leetcode

题意：

给一个无序的，可能有重复的数组。找出其中的数字组合使其之和等于给定数，组合里不能重复使用数组中的某个数，组合之间所包含的值不能相等。

分析：

这个题就是深搜就可以了。但是关键在于如何避免重复：

三个：

第一个

避免两次使用同一个数：每次遍历都从已经放入的数之后

即：     for(int i = start; ...;.....){} 

第二个，对数组排序，避免组合内容重复

比如 1   2   5   1

如果不排序 1   2   5   .   2  5   1都是合法的搜索，但是内容重复

即Arrays.sort( arr );

第三个，略过重复的数字

比如排好序的  1   1   2   5

任然可能两次 1   2  5 ，  1  2   5

即： if (i > start && arr[i] == arr[i-1])                 continue;                     

完整代码：

public class Solution { List<Integer> l = null; List<List<Integer>> list = null; int target; int[] arr; public List<List<Integer>> combinationSum2(int[] candidates, int target) { l = new ArrayList<>(); list = new ArrayList<>(); arr = candidates; Arrays.sort(arr); //2 this.target = target; dfs(0, 0); return list; } private void dfs(int sum, int start){ if(sum >= target){ if(sum==target) list.add(new ArrayList(l)); return; } for(int i=start; i<arr.length; i++){ //1 if (i > start && arr[i] == arr[i-1]) //3 continue; l.add(arr[i]); dfs(sum + arr[i], i+1); l.remove(l.size()-1); } } }