40. Combination Sum II LeetCode Solution

In this guide we will provide 40. Combination Sum II LeetCode Solution with best time and space complexity. The solution to Combination Sum II problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Problem Statement

Complexity Analysis

Combination Sum II solution in C++
Combination Sum II soution in Java
Combination Sum II solution Python
Additional Resources

40. Combination Sum II LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(n \cdot 2^n)
Space Complexity: O(n + n \cdot 2^n) = O(n \cdot 2^n)

40. Combination Sum II LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int>> ans;
    ranges::sort(candidates);
    dfs(candidates, 0, target, {}, ans);
    return ans;
  }

 private:
  void dfs(const vector<int>& A, int s, int target, vector<int>&& path,
           vector<vector<int>>& ans) {
    if (target < 0)
      return;
    if (target == 0) {
      ans.push_back(path);
      return;
    }

    for (int i = s; i < A.size(); ++i) {
      if (i > s && A[i] == A[i - 1])
        continue;
      path.push_back(A[i]);
      dfs(A, i + 1, target - A[i], std::move(path), ans);
      path.pop_back();
    }
  }
};
/* code provided by PROGIEZ */

40. Combination Sum II LeetCode Solution in Java

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

  private void dfs(int s, int[] candidates, int target, List<Integer> path,
                   List<List<Integer>> ans) {
    if (target < 0)
      return;
    if (target == 0) {
      ans.add(new ArrayList<>(path));
      return;
    }

    for (int i = s; i < candidates.length; ++i) {
      if (i > s && candidates[i] == candidates[i - 1])
        continue;
      path.add(candidates[i]);
      dfs(i + 1, candidates, target - candidates[i], path, ans);
      path.remove(path.size() - 1);
    }
  }
}
// code provided by PROGIEZ

40. Combination Sum II LeetCode Solution in Python

class Solution:
  def combinationSum2(self, candidates: list[int],
                      target: int) -> list[list[int]]:
    ans = []

    def dfs(s: int, target: int, path: list[int]) -> None:
      if target < 0:
        return
      if target == 0:
        ans.append(path.copy())
        return

      for i in range(s, len(candidates)):
        if i > s and candidates[i] == candidates[i - 1]:
          continue
        path.append(candidates[i])
        dfs(i + 1, target - candidates[i], path)
        path.pop()

    candidates.sort()
    dfs(0, target, [])
    return ans
 #code by PROGIEZ