40. Combination Sum II --【M】Backtracking / Snapchat
https://leetcode.com/problems/combination-sum-ii/
http://wdxtub.com/interview/14520604911420.html
21ms 73.56%
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null || candidates.length == 0)
return result;
Arrays.sort(candidates);
helper(result, new ArrayList<Integer>(), candidates, target, 0);
return result;
}
public void helper(List<List<Integer>> result, List<Integer> list, int[] candidates, int target, int start) {
if (target == 0) {
result.add(new ArrayList<Integer>(list));
return;
}
for (int i = start; i < candidates.length && target >= candidates[i]; i++) {
if (i != start && candidates[i-1] == candidates[i]) ///
continue;
list.add(candidates[i]);
helper(result, list, candidates, target - candidates[i], i + 1);
list.remove(list.size() - 1);
}
}
}
*总结：
本质：已知带重复元素的数组，求不同combination，里面元素之和== target。条件是同一个元素不可重用。经典思路：backtracking dfs 。注意两个去重点。
具体：已知数组本就是有重复的，想避免重复解，除了start + 1之外还需要if (i != start && A[i-1] == A[i] ) continue;
注意：如果没有那个判断结果就是这样的：