77 从1~n 中产生K个组合， 因为1~n 没有重复元素，所以很简单
class Solution { public List > combine(int n, int k) { int[] nums= new int[n]; for(int i=1; i<=n; i++){ nums[i-1] = i; } List > result = new ArrayList<>(); dfs(new ArrayList<>(), 0, nums,k,result); return result; } private void dfs(List curResult, int start, int[] nums, int k, List > result){ if(curResult.size() == k){ result.add(new ArrayList<>(curResult)); return; } for(int i=start; i
39.
前提： 1. 所有数都是positive的 2. 所有数没有duplicated的
并且一个数可以重复选择
Input: candidates = [2,3,6,7], target = 7,A solution set is:[ [7], [2,2,3]] 算法： 就是简单的组合问题，唯一需要注意的是， 从左往右看， 对于2, 选了3 后 变成 [2 3] ，那么对于3 就不能再选2了。 换句话说， 每次只能添加 index >= current_index的， 如果不允许重复添加，那条件就是index > current_index才行。 算法的递归树如下所示：
class Solution { public List > combinationSum(int[] candidates, int target) { List > result = new ArrayList<>(); dfs(0, new ArrayList (), result,0,target,candidates); return result; } private void dfs(int start, List curResult, List > result,int sum, int target,int[] nums){ if(sum> target) return; if(sum== target) { result.add(new ArrayList<>(curResult)); return; } for(int i=start; i
40.
1. 条件变成了 数字有重复 ， 有重复的处理方法都是先排序。
2. 并且返回结果仍然需要unique 的组合
3. 每个数字只能被放一次， 和39不同稍微改一下 递归时条件 从index = cur_index+1 放 就不会重复了
Input: candidates = [10,1,2,7,6,1,5], target = 8,A solution set is:[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]] 画出的递归树如下：
class Solution { public List > combinationSum2(int[] candidates, int target) { List > result = new ArrayList<>(); Arrays.sort(candidates); dfs(0, new ArrayList (), result,0,target,candidates); return result; } private void dfs(int start, List curResult, List > result,int sum, int target,int[] nums){ if(sum >= target){ if(sum>target) return; else { result.add(new ArrayList<>(curResult)); return; } } for(int i=start; i start && nums[i] == nums[i-1]) continue; curResult.add(nums[i]); sum+=nums[i]; dfs(i+1, curResult,result,sum,target,nums);// 每个数字只能被放一次， 因此得从 i+1开始 curResult.remove(curResult.size()-1); sum-=nums[i]; } }}
216
从1-9里选k 个数， 组成的和为n。 和39基本一样，只是 dfs 返回的条件略有不同而已。
Input: k = 3, n = 7Output: [[1,2,4]]
class Solution { public List > combinationSum3(int k, int n) { int[] nums = {1,2,3,4,5,6,7,8,9}; List > result = new ArrayList<>(); dfs(0,k,n,nums,new ArrayList<>(), 0, result); return result; } private void dfs(int start, int k, int n, int[] nums, List curResult, int sum, List > result){ if(sum > n || curResult.size() >k) return; if(sum == n && curResult.size() == k){ result.add(new ArrayList<>(curResult)); return; } for(int i= start; i