题目大意：输出所有用k个数的和为n的组合。可以使用的元素是1到9。
Problem:
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:
|
1 |
[[1,2,4]] |
Example 2:
Input: k = 3, n = 9
Output:
|
1 |
[[1,2,6], [1,3,5], [2,3,4]] |
Idea:
DFS + backtracking
bit
Solution:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua // Runtime: 0 ms class Solution { public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> ans; vector<int> cur; dfs(k, n, 1, cur, ans); return ans; } private: // Use k numbers (>= s) to sum up to n void dfs(int k, int n, int s, vector<int>& cur, vector<vector<int>>& ans) { if (k == 0) { if (n == 0) ans.push_back(cur); return; } for (int i = s; i <= 9; ++i) { if (i > n) return; cur.push_back(i); dfs(k - 1, n - i, i + 1, cur, ans); cur.pop_back(); } } }; |
C++ / binary
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
class Solution { public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> ans; // 2^9, generate all combinations of [1 .. 9] for (int i = 0; i < (1 << 9); ++i) { vector<int> cur; int sum = 0; // Use j if (j - 1)-th bit is 1 for (int j = 1; j <= 9; ++j) if (i & (1 << (j - 1))) { sum += j; cur.push_back(j); } if (sum == n && cur.size() == k) ans.push_back(cur); } return ans; } }; |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution: def combinationSum3(self, k, n): def dfs(k, n, s, cur, ans): if k == 0 and n == 0: ans.append(list(cur)) for i in range(s, min(n + 1, 10)): dfs(k - 1, n - i, i + 1, cur + [i], ans) ans = [] dfs(k, n, 1, [], ans) return ans |
Related problems: