题目
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
解题
class Solution { public: vector<vector<int>> res; vector<int> path; void backtracing(int k,int n,int sum,int startIndex){ if(path.size()==k){ if(sum==n) res.push_back(path); return; } for(int i=startIndex;i<=9;i++){ path.push_back(i); sum+=i; backtracing(k,n,sum,i+1); sum-=i; path.pop_back(); } } vector<vector<int>> combinationSum3(int k, int n) { backtracing(k,n,0,1); return res; } };
剪枝后
class Solution { public: vector<vector<int>> res; vector<int> path; void backtracing(int k,int n,int sum,int startIndex){ if(path.size()==k){ if(sum==n) res.push_back(path); return; } for(int i=startIndex;i<=9-(k-path.size())+1;i++){//剪枝 path.push_back(i); sum+=i; //剪枝 if(sum>n){ sum-=i; path.pop_back(); return; } backtracing(k,n,sum,i+1); sum-=i; path.pop_back(); } } vector<vector<int>> combinationSum3(int k, int n) { backtracing(k,n,0,1); return res; } };
java
class Solution { List<List<Integer>> res=new LinkedList<>(); List<Integer> path=new LinkedList<>(); void dfs(int startIndex,int sum,int k,int target){ if(path.size()==k){ if(sum==target){ res.add(new LinkedList<Integer>(path)); } return; }else if(sum>target) return; for(int i=startIndex;i<=9;i++){ path.add(i); dfs(i+1,sum+i,k,target); path.remove(path.size()-1); } } public List<List<Integer>> combinationSum3(int k, int n) { dfs(1,0,k,n); return res; } }
