Combination Sum II 40

Description

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Hint

backtracking sort firstly

Method

Time & Space

o(n ^ avg high)

Code

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
           List<List<Integer>> ans = new ArrayList<List<Integer>>();
           Arrays.sort(candidates);
           permutation(candidates, target, 0, ans, new ArrayList<Integer>());
           return ans;
    }

    private void permutation(int[] candidates, int target, int pos,
                             List<List<Integer>> ans,
                             List<Integer> list){
                 if (target == 0){
                     ans.add(new ArrayList<Integer>(list));
                     return;
                 } 
                 for (int i = pos; i < candidates.length && candidates[i] <= target; i++){
                      if (i > pos && candidates[i] == candidates[i - 1]){
                          continue;
                      }
                      list.add(candidates[i]);
                      permutation(candidates, target - candidates[i], i + 1, ans, list);
                      list.remove(list.size() - 1);
                 }

    }
}