aboutsummaryrefslogtreecommitdiff
path: root/other/combination_sum3.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/combination_sum3.cpp')
-rw-r--r--other/combination_sum3.cpp38
1 files changed, 38 insertions, 0 deletions
diff --git a/other/combination_sum3.cpp b/other/combination_sum3.cpp
new file mode 100644
index 0000000..bde03a3
--- /dev/null
+++ b/other/combination_sum3.cpp
@@ -0,0 +1,38 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ vector<vector<int>> combinationSum3(int k, int n) {
+ vector<vector<int>> ans;
+ vector<int> sol;
+ helper(ans, sol, k, n);
+ return ans;
+ }
+ void print(vector<vector<int>> &ans) {
+ for (int i = 0; i < ans.size(); i++)
+ for (int j = 0; j < ans.size(); j++)
+ cout << ans[i][j] << ' ';
+ }
+
+private:
+ void helper(vector<vector<int>> &ans, vector<int> sol, int k, int n) {
+ if (sol.size() == k && n == 0) {
+ ans.push_back(sol);
+ return;
+ }
+ if (sol.size() < k)
+ for (int i = sol.empty() ? 1 : sol.back() + 1; i <= 9; ++i) {
+ if (n - i < 0)
+ break;
+ sol.push_back(i);
+ helper(ans, sol, k, n - i);
+ sol.pop_back();
+ }
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<vector<int>> ans;
+ obj.print(ans);
+}