Combination Sum II
Program for Printing all Combination Sum
You are given an array of integers candidates, which may have duplicate numbers, and a target number target. Your goal is to find all unique combinations of numbers from the array that add up to the target.
Each number from the array can only be used once in each combination. The solution should not have any duplicate combinations.
You can return the combinations in any order, and the numbers in each combination can be in any order as well.
Example 1
Input: candidates = [9,2,2,4,6,1,5], target = 8
Output: [
[1,2,5],
[2,2,4],
[2,6]
]
Output: [
[1,2,5],
[2,2,4],
[2,6]
]
Example 2
Input: candidates = [1,2,3,4,5], target = 7
Output: [
[1,2,4],
[2,5],
[3,4]
]
Output: [
[1,2,4],
[2,5],
[3,4]
]
Constraints:
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
Program for Printing all Combinational Sum II Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(n * (2^n)) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
Instead of using a hash set to remove duplicates, sort the array. Sorting helps identify and skip duplicate combinations during recursion.
Hint 2 :
Use backtracking to find combinations that sum to the target. Sorting the array lets you skip duplicate elements, ensuring unique combinations.
Hint 3 :
Recursively traverse the array from index “i”, adding elements to the combination if the sum doesn’t exceed the target. After processing an element, skip duplicates to avoid repeated combinations.
There are mainly 4 approach to solve this problem-
- Brute Force Method
- Backtracking Method
- Backtracking(Hash Map) Method
- Backtracking(Optimal) Method
1. Brute Force Method
This approach generates all possible combinations of the array and then filters out duplicates using a hash set or other data structures. While simple, it is highly inefficient due to the large number of unnecessary computations.
- Time complexity: O(n* 2^n)
- Space complexity: O(2^n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
set<vector<int>> res;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
res.clear();
sort(candidates.begin(), candidates.end());
vector<int> cur;
generateSubsets(candidates, target, 0, cur, 0);
return vector<vector>(res.begin(), res.end());
}
private:
void generateSubsets(vector<int>& candidates, int target, int i, vector<int>& cur, int total) {
if (total == target) {
res.insert(cur);
return;
}
if (total > target || i == candidates.size()) {
return;
}
cur.push_back(candidates[i]);
generateSubsets(candidates, target, i + 1, cur, total + candidates[i]);
cur.pop_back();
generateSubsets(candidates, target, i + 1, cur, total);
}
};
Java
public class Solution {
private Set<List<Integer>> res;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
res = new HashSet<>();
Arrays.sort(candidates);
generateSubsets(candidates, target, 0, new ArrayList<>(), 0);
return new ArrayList<>(res);
}
private void generateSubsets(int[] candidates, int target, int i, List<Integer> cur, int total) {
if (total == target) {
res.add(new ArrayList<>(cur));
return;
}
if (total > target || i == candidates.length) {
return;
}
cur.add(candidates[i]);
generateSubsets(candidates, target, i + 1, cur, total + candidates[i]);
cur.remove(cur.size() - 1);
generateSubsets(candidates, target, i + 1, cur, total);
}
}
Python
class Solution:
def combinationSum2(self, candidates, target):
res = set()
candidates.sort()
def generate_subsets(i, cur, total):
if total == target:
res.add(tuple(cur))
return
if total > target or i == len(candidates):
return
cur.append(candidates[i])
generate_subsets(i + 1, cur, total + candidates[i])
cur.pop()
generate_subsets(i + 1, cur, total)
generate_subsets(0, [], 0)
return [list(combination) for combination in res]
JavaScript
class Solution {
constructor() {
this.res = new Set();
}
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
combinationSum2(candidates, target) {
this.res.clear();
candidates.sort((a, b) => a - b);
this.generateSubsets(candidates, target, 0, [], 0);
return Array.from(this.res, subset => JSON.parse(subset));
}
/**
* @param {number[]} candidates
* @param {number} target
* @param {number} i
* @param {number[]} cur
* @param {number} total
* @return {void}
*/
generateSubsets(candidates, target, i, cur, total) {
if (total === target) {
this.res.add(JSON.stringify([...cur]));
return;
}
if (total > target || i === candidates.length) {
return;
}
cur.push(candidates[i]);
this.generateSubsets(candidates, target, i + 1, cur, total + candidates[i]);
cur.pop();
this.generateSubsets(candidates, target, i + 1, cur, total);
}
}
2. Backtracking Method
In this method, recursion is used to explore all combinations by adding elements to a current path and checking if their sum equals the target. Sorting the array beforehand helps to skip duplicate elements and ensures unique combinations.
- Time complexity: O(n* 2^n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
res.clear();
sort(candidates.begin(), candidates.end());
vector<int> cur;
dfs(candidates, target, 0, cur, 0);
return res;
}
private:
void dfs(vector<int>& candidates, int target, int i, vector<int>& cur, int total) {
if (total == target) {
res.push_back(cur);
return;
}
if (total > target || i == candidates.size()) {
return;
}
cur.push_back(candidates[i]);
dfs(candidates, target, i + 1, cur, total + candidates[i]);
cur.pop_back();
while (i + 1 < candidates.size() && candidates[i] == candidates[i + 1]) {
i++;
}
dfs(candidates, target, i + 1, cur, total);
}
};
Java
public class Solution {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtrack(0, new ArrayList<>(), nums);
return res;
}
private void backtrack(int i, List<Integer> subset, int[] nums) {
if (i == nums.length) {
res.add(new ArrayList<>(subset));
return;
}
subset.add(nums[i]);
backtrack(i + 1, subset, nums);
subset.remove(subset.size() - 1);
while (i + 1 < nums.length && nums[i] == nums[i + 1]) {
i++;
}
backtrack(i + 1, subset, nums);
}
}
Python
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
def backtrack(i, subset):
if i == len(nums):
res.append(subset[::])
return
subset.append(nums[i])
backtrack(i + 1, subset)
subset.pop()
while i + 1 < len(nums) and nums[i] == nums[i + 1]:
i += 1
backtrack(i + 1, subset)
backtrack(0, [])
return res
JavaScript
class Solution {
/**
* @param {number[]} nums
* @return {number[][]}
*/
subsetsWithDup(nums) {
const res = [];
nums.sort((a, b) => a - b);
this.backtrack(0, [], nums, res);
return res;
}
/**
* @param {number} start
* @param {number[]} subset
* @param {number[]} nums
* @param {number[][]} res
* @return {void}
*/
backtrack(start, subset, nums, res) {
res.push([...subset]);
for (let i = start; i < nums.length; i++) { if (i > start && nums[i] === nums[i - 1]) {
continue;
}
subset.push(nums[i]);
this.backtrack(i + 1, subset, nums, res);
subset.pop();
}
}
}
3. Backtracking(Hash Map) Method
This approach uses a hash map to keep track of elements and their counts. During recursion, the hash map ensures no element is used more than its count in the array, avoiding duplicates and keeping the solution efficient.
- Time complexity: O(n* 2^n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<vector<int>> res;
unordered_map<int, int> count;
vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
vector<int> cur;
vector<int> A;
for (int num : nums) {
if (!count[num]) {
A.push_back(num);
}
count[num]++;
}
backtrack(A, target, cur, 0);
return res;
}
void backtrack(vector<int>& nums, int target, vector<int>& cur, int i) {
if (target == 0) {
res.push_back(cur);
return;
}
if (target < 0 || i >= nums.size()) {
return;
}
if (count[nums[i]]) {
cur.push_back(nums[i]);
count[nums[i]]--;
backtrack(nums, target - nums[i], cur, i);
count[nums[i]]++;
cur.pop_back();
}
backtrack(nums, target, cur, i + 1);
}
};
Java
public class Solution {
List<List<Integer>> res = new ArrayList<>();
Map<Integer, Integer> count = new HashMap<>();
public List<List<Integer>> combinationSum2(int[] nums, int target) {
List<Integer> cur = new ArrayList<>();
List<Integer> A = new ArrayList<>();
for (int num : nums) {
if (!count.containsKey(num)) {
A.add(num);
}
count.put(num, count.getOrDefault(num, 0) + 1);
}
backtrack(A, target, cur, 0);
return res;
}
private void backtrack(List<Integer> nums, int target, List<Integer> cur, int i) {
if (target == 0) {
res.add(new ArrayList<>(cur));
return;
}
if (target < 0 || i >= nums.size()) {
return;
}
if (count.get(nums.get(i)) > 0) {
cur.add(nums.get(i));
count.put(nums.get(i), count.get(nums.get(i)) - 1);
backtrack(nums, target - nums.get(i), cur, i);
count.put(nums.get(i), count.get(nums.get(i)) + 1);
cur.remove(cur.size() - 1);
}
backtrack(nums, target, cur, i + 1);
}
}
Python
class Solution:
def combinationSum2(self, nums, target):
self.res = []
self.count = defaultdict(int)
cur = []
A = []
for num in nums:
if self.count[num] == 0:
A.append(num)
self.count[num] += 1
self.backtrack(A, target, cur, 0)
return self.res
def backtrack(self, nums, target, cur, i):
if target == 0:
self.res.append(cur.copy())
return
if target < 0 or i >= len(nums):
return
if self.count[nums[i]] > 0:
cur.append(nums[i])
self.count[nums[i]] -= 1
self.backtrack(nums, target - nums[i], cur, i)
self.count[nums[i]] += 1
cur.pop()
self.backtrack(nums, target, cur, i + 1)
JavaScript
class Solution {
constructor() {
this.res = [];
this.count = new Map();
}
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
combinationSum2(nums, target) {
const cur = [];
const A = [];
for (const num of nums) {
if (!this.count.has(num)) {
A.push(num);
}
this.count.set(num, (this.count.get(num) || 0) + 1);
}
this.backtrack(A, target, cur, 0);
return this.res;
}
/**
* @param {number[]} nums
* @param {number} target
* @param {number[]} cur
* @param {number} i
* @return {void}
*/
backtrack(nums, target, cur, i) {
if (target === 0) {
this.res.push([...cur]);
return;
}
if (target < 0 || i >= nums.length) {
return;
}
if (this.count.get(nums[i]) > 0) {
cur.push(nums[i]);
this.count.set(nums[i], this.count.get(nums[i]) - 1);
this.backtrack(nums, target - nums[i], cur, i);
this.count.set(nums[i], this.count.get(nums[i]) + 1);
cur.pop();
}
this.backtrack(nums, target, cur, i + 1);
}
}
4. Backtracking(Optimal) Method
This optimized approach involves sorting the array and using recursion to build combinations. Duplicate elements are skipped by comparing each element with the previous one, ensuring no duplicate combinations are generated. It is efficient in both time and space.
- Time complexity: O(n* 2^n)
- Space complexity: O(n)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
res.clear();
sort(candidates.begin(), candidates.end());
dfs(0, {}, 0, candidates, target);
return res;
}
private:
void dfs(int idx, vector<int> path, int cur, vector<int>& candidates, int target) {
if (cur == target) {
res.push_back(path);
return;
}
for (int i = idx; i < candidates.size(); i++) { if (i > idx && candidates[i] == candidates[i - 1]) {
continue;
}
if (cur + candidates[i] > target) {
break;
}
path.push_back(candidates[i]);
dfs(i + 1, path, cur + candidates[i], candidates, target);
path.pop_back();
}
}
};
Java
public class Solution {
private static List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
res.clear();
Arrays.sort(candidates);
dfs(0, new ArrayList<>(), 0, candidates, target);
return res;
}
private static void dfs(int idx, List<Integer> path, int cur, int[] candidates, int target) {
if (cur == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = idx; i < candidates.length; i++) { if (i > idx && candidates[i] == candidates[i - 1]) {
continue;
}
if (cur + candidates[i] > target) {
break;
}
path.add(candidates[i]);
dfs(i + 1, path, cur + candidates[i], candidates, target);
path.remove(path.size() - 1);
}
}
}
Python
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
candidates.sort()
def dfs(idx, path, cur):
if cur == target:
res.append(path.copy())
return
for i in range(idx, len(candidates)):
if i > idx and candidates[i] == candidates[i - 1]:
continue
if cur + candidates[i] > target:
break
path.append(candidates[i])
dfs(i + 1, path, cur + candidates[i])
path.pop()
dfs(0, [], 0)
return res
JavaScript
class Solution {
constructor() {
this.res = [];
}
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
combinationSum2(candidates, target) {
this.res = [];
candidates.sort((a, b) => a - b);
const dfs = (idx, path, cur) => {
if (cur === target) {
this.res.push([...path]);
return;
}
for (let i = idx; i < candidates.length; i++) { if (i > idx && candidates[i] === candidates[i - 1]) {
continue;
}
if (cur + candidates[i] > target) {
break;
}
path.push(candidates[i]);
dfs(i + 1, path, cur + candidates[i]);
path.pop();
}
};
dfs(0, [], 0);
return this.res;
}
}
