Combination Sum II

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:

Java
JavaScript
Python
C++

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;
            }
        }
    }
}

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  const result = [];
  candidates.sort((a, b) => a - b);
  helper(
    candidates,
    0,
    target,
    0,
    [],
    result,
    Array(candidates.length).fill(false)
  );
  return result;
};
function helper(
  candidates,
  currentSum,
  target,
  start,
  currentList,
  result,
  selected
) {
  if (currentSum === target) {
    result.push(currentList.slice());
    return;
  }
  for (let i = start; i < candidates.length; ++i) {
    if (
      target >= currentSum + candidates[i] &&
      (i === 0 || candidates[i - 1] !== candidates[i] || selected[i - 1])
    ) {
      currentList.push(candidates[i]);
      selected[i] = true;
      helper(
        candidates,
        currentSum + candidates[i],
        target,
        i + 1,
        currentList,
        result,
        selected
      );
      currentList.pop();
      selected[i] = false;
    }
  }
}

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()
        self.helper(candidates, 0, target, 0, [], result, [False] * len(candidates))
        return result

    def helper(self, candidates: List[int], currentSum: int, target: int, start: int, currentList: List[int], result: List[List[int]], selected: List[bool]) -> None:
        if currentSum == target:
            result.append(currentList[:])
            return
        for i in range(start, len(candidates)):
            if target >= currentSum + candidates[i] and (i == 0 or candidates[i - 1] != candidates[i] or selected[i - 1]):
                currentList.append(candidates[i])
                selected[i] = True
                self.helper(candidates, currentSum + candidates[i], target, i + 1, currentList, result, selected)
                currentList.pop()
                selected[i] = False

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        sort(candidates.begin(), candidates.end());
        vector<int> currentList;
        vector<bool> selected(candidates.size(), false);
        helper(candidates, 0, target, 0, currentList, result, selected);
        return result;
    }
private:
    void helper(const vector<int>& candidates, int currentSum, int target, int start, vector<int> currentList, vector<vector<int>>& result, vector<bool>& selected) {
        if (currentSum == target) {
            result.push_back(currentList);
            return;
        }
        for (int i = start; i < candidates.size(); ++i) {
            if (target >= currentSum + candidates[i] && (i == 0 || candidates[i - 1] != candidates[i] || selected[i - 1])) {
                currentList.push_back(candidates[i]);
                selected[i] = true;
                helper(candidates, currentSum + candidates[i], target, i + 1, currentList, result, selected);
                currentList.pop_back();
                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.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​