King Of Interviews

Combination Sum II: Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

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

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

Constraints:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

Try this Problem on your own or check similar problems:

Solution:

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

    private void helper(int[] candidates, int currentSum, int target, int start, List<Integer> currentList, List<List<Integer>> result, boolean[] selected){
        if(currentSum == target){
            result.add(new ArrayList<>(currentList));
            return;
        }
        for(int i = start; i < candidates.length; ++i){
            if(target >= currentSum + candidates[i] &&
            (i == 0 || candidates[i-1] != candidates[i] || selected[i-1])){
                currentList.add(candidates[i]);
                selected[i] = true;
                helper(candidates, currentSum + candidates[i], target, i + 1, currentList, result, selected);
                currentList.remove(currentList.size() - 1);
                selected[i] = false;
            }
        }
    }
}

Time/Space Complexity:

Time Complexity: O(n*2^n)
Space Complexity: O(n)

Explanation:

Almost identical to Combination Sum but with a twist that we can’t pick number more than once (notice that loop starts from start which is increasing in every recursion call). For eliminating duplicates we did the exact same trick as in Permutations II , we sort the array and check if the previous element has been included (case when we have nums[i] == nums[i-1]) in case we have two same adjacent elements in the sorted array, thus allowing us to omit duplicate combinations. The same logic of backtracking is done after, we add the candidate to the currentList, we mark it as selected and call the helper recursively, after that we backtrack, remove the element from the list and mark it as “not selected”. Since we can have at most all n elements selected, the recursion tree is n levels deep, while for each element we have to choose either to select it or omit it leading to O(n*2^n) where n is the maximum size of the combination we’re copying over. For the space complexity we have O(n) corresponding to the maximum size of currentList.

Combination Sum II