leetcode中等难度 第39+40题 组合总合

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。 解集不能包含重复的组合。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

39题，回溯+剪枝

class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { int len = candidates.length ; List<List<Integer>> ans = new ArrayList<>(); Deque<Integer> path = new ArrayDeque<>(); Arrays.sort(candidates); dfs(candidates,len,target,0,path,ans); return ans ; } public void dfs(int[] candidates,int length,int target,int begin, Deque<Integer> path,List<List<Integer>> ans){ if(target == 0){ ans.add(new ArrayList<>(path)); return ; } for(int i = begin ; i < length ; i ++){ if(target < candidates[i]){ break ; } path.addLast(candidates[i]); dfs(candidates,length,target-candidates[i],i,path,ans); path.removeLast(); } } }

接下来是40题，唯一的不同是，不能用相同的元素。

class Solution { public List<List<Integer>> combinationSum2(int[] candidates, int target) { int len = candidates.length ; List<List<Integer>> ans = new ArrayList<>(); Arrays.sort(candidates); Deque<Integer> path = new ArrayDeque<>(); dfs(candidates,len,target,0,path,ans); return ans ; } public void dfs(int[] candidates,int len,int target,int begin,Deque<Integer> path,List<List<Integer>> ans){ if(target == 0){ ans.add(new ArrayList<>(path)); return ; } for(int i = begin ; i < len ; i ++){ if(target < candidates[i]){ break ; } if(i > begin && candidates[i] == candidates[i-1] ){ continue ; } path.addLast(candidates[i]); dfs(candidates,len,target-candidates[i],i+1,path,ans); path.removeLast(); } } }

递归的思想。还是要多练习啊，怎么去重什么的。