[leetcode] Combination Sum 2 | 给个数组，找里面能求和=x的所有组合（数字只能用一次，结果不能重复）

Posted by: lexigrey on: October 9, 2013

• In: leetcode
• Leave a Comment

比如 {1, 1, 1, 2, 3}，x = 3, 结果就是{111}{12}{3}。这个题挺难想的，和上一题又不一样。正常stack，把1push进去，然后直接在2上recurse x=2的（因为1只能用一次）。这样一直做到x==0。这样就会有重复：当stack pop空了之后，回到第二个1上，又开始push，那stack的第0个又是1了，刚才已经做过stack第0个是1的一遍了（左边的一遍肯定包括了最多种的情况），所以现在再把1放里面就会重复。所以要在做“要不要在当前layer试一下下一个数？”的决定的时候，要看“下一个数和当前数是否相等？因为当前数已经做过了，同一层layer说明是同一个position，再放当前数就会重复）。

总结：

• combination/set: 用stack，因为长度不固定。
• permutation: 用int[]，keep一个pos pointer。
• 主函数里面不要循环，就一个以初始值call副函数的语句就行。
• 副函数是循环里面call自己。

public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  Stack<Integer> path = new Stack<Integer>();
  combinationSum(num, target, 0, path, result);
  return result;
}
private void combinationSum(int[] arr, int target, int start, Stack<Integer> path, ArrayList<ArrayList<Integer>> result) {
  if (target == 0) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.addAll(path);
    result.add(list);
    return;
  }
  for (int i = start; i < arr.length; i++) {
    if (arr[i] > target)
      return;
    path.push(arr[i]);
    combinationSum(arr, target - arr[i], i + 1, path, result);
    path.pop();
    //do we want to place arr[i + 1] at the same position arr[i] has been?
    while (i + 1 < arr.length && arr[i] == arr[i + 1]) {
      i++;
    }
  }
}

Tags: dfs, duplicate, hard, subsets/permutation, 固定解法