40. Combination Sum II

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

Each number inCmay only be usedoncein 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 target8,
A solution set is:

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

Analysis:

DFS.

The key to not using same element twice is:

every time when it calls next level recursion, pos+1, so it always start with next one.

The key to not having duplicate solution is:

at each level, we know we will loop through all elements left, but we need to make sure, if one element is used to go further in dfs, we not gonna use it again at the same level. So we need to sort the array and either use a set<Integer> to keep track each recursion what has been used, Or simply check if current element equals to previous one(since we have sorted the array, duplicates will be adjacent to each other)

Complexity:

Time: ?

Space: ?

Code:

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> returnList = new ArrayList<List<Integer>>();
        if(candidates == null || candidates.length == 0){
            return returnList;
        }
        Arrays.sort(candidates);
        dfs(target, 0, candidates, new ArrayList<Integer>(), returnList);
        return returnList;
    }

    private void dfs(int target, int pos, int[] nums, List<Integer> tempList, List<List<Integer>> returnList){
        if(target == 0){
            returnList.add(new ArrayList<Integer>(tempList));
            return;
        }

        for(int i = pos; i < nums.length; i++){
            if(i > pos && nums[i] == nums[i-1]) continue;
            if(target >= nums[i]){
                tempList.add(nums[i]);
                dfs(target - nums[i], i+1, nums, tempList, returnList);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}