diff options
Diffstat (limited to 'other/combination_sum3.cpp')
-rw-r--r-- | other/combination_sum3.cpp | 38 |
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); +} |