Combination Sum II

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

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

Have you met this question in a real interview? 

Yes

Example

For example, given candidate set 10,1,6,7,2,1,5 and target 8,

A solution set is: 

[1,7]

[1,2,5]

[2,6]

[1,1,6]

Note

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

public class Solution {

    /**

     * @param num: Given the candidate numbers

     * @param target: Given the target number

     * @return: All the combinations that sum to target

     */

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        // write your code here

        List<List<Integer>> res = new ArrayList<List<Integer>>();

        Arrays.sort(candidates);

        combinationSum(res, 0, candidates, new ArrayList<Integer>(), target);

        return res;

        

    }

    private void combinationSum(List<List<Integer>> res, int start, int[] candidates, List<Integer> sub, int target){

        if(target == 0){

            res.add(new ArrayList<Integer>(sub));

            return;

        }

        

        for(int i = start; i < candidates.length; i++){

            if(i > start && candidates[i] == candidates[i-1]) continue;

            if(candidates[i] <= target){

                sub.add(candidates[i]);

                combinationSum(res, i+1, candidates, sub, target-candidates[i]);

                sub.remove(sub.size()-1);

            }

        }

    }

}