Combination Sum — Pick and Stay

Assume an array: [9, 2, 3, 5]

and a target sum: 9

We need to find all possible combinations whose sum equals the target.

One important condition is that we are allowed to use the same element multiple times.

For example, if the array contains 3, we can use: [3,3,3]

because: 3 + 3 + 3 = 9

Concept

This problem can be solved using Backtracking.

In the Subset problem, we had two choices for every element:

• Pick
• Not Pick

The same idea applies here, but with one small modification.

For every element, we have two choices:

1. Pick the element and stay at the same index.
2. Skip the element and move to the next index.

Why do we stay at the same index after picking?

Because the problem allows us to use the same element multiple times.

This is the key difference between Subset and Combination Sum.

Subset: Pick -> i + 1 Not Pick -> i + 1

Combination Sum: Pick -> i Not Pick -> i + 1

Base Conditions

If the target becomes: 0

we have found a valid combination.

Add the current subset to the result.

If: target < 0

or i >= nums.length

there is no valid answer along this path, so we return.

Approach

We first add the current element to the subset.

Then we recursively call the function while staying at the same index and reducing the target.

After exploring that path, we remove the element from the subset (Backtracking).

Finally, we explore the path where we ignore the current element and move to the next index.

Dry Run

Dry Run For Combination Sum

Code

List<List<Integer>> res=new ArrayList<>();

public void backtrack(int i, int[]nums, List<Integer> set, int target){

if(target==0){

res.add(new ArrayList<>(set));

return;

}

if(target < 0 || i ≥ nums.length){

return;

}

set.add(nums[i]);

backtrack(i, nums, set, target — nums[i]);

set.remove(set.size()-1);

backtrack(i+1, nums, set, target);

}

List<List<Integer>> combinationSum (int[]nums, int target){

backtrack(0,nums,new ArrayList<>(), target);

return res;

}

What If the Array Contains Duplicates?

So far, in Combination Sum, we were allowed to:

• Use the same element multiple times.
• Assume there were no duplicate values in the array.

But what if the array contains duplicate elements and each element can be used only once?

For example: [1, 1, 2, 5, 6, 7, 10]

Target: 8

Now the problem becomes a combination of:

• Subset II (because duplicates are present)
• Combination Sum (because we need subsets whose sum equals the target)

Key Changes

1. Sort the Array

First, we sort the array.

Arrays.sort(nums);

Sorting brings duplicate elements together, making them easier to skip.

2. Base Conditions

If: target == 0

we have found a valid combination.

Add the current subset to the result list.

If: target < 0 || i >= nums.length

there is no valid solution along this path, so we return.

3. Pick the Current Element

Add the current element to the subset.

set.add(nums[i]);

Unlike Combination Sum I, we cannot reuse the same element.

Therefore, after picking it, we move to the next index.

backtrack(i + 1, nums, set, target — nums[i])

4. Backtrack

Remove the element before exploring the next choice.

set.remove(set.size() — 1);

5. Skip Duplicates

Before exploring the “Not Pick” path, skip all consecutive duplicate elements.

while(i + 1 < nums.length && nums[i] == nums[i + 1]) { i++; }

This ensures that duplicate combinations are not generated.

6. Explore the Not Pick Path

After skipping duplicates, move to the next distinct element.

backtrack(i + 1, nums, set, target);

Complexity

Time Complexity : O(2^(target/min(nums)))

The recursion tree can grow exponentially because each element can be chosen multiple times.

For interview purposes, it is usually stated as: Exponential

Space Complexity : O(target/min(nums))

This is the maximum recursion depth when we repeatedly pick the smallest element.

Conclusion

Combination Sum is a slight variation of the Subset problem.

Instead of moving to the next index after picking an element, we stay at the same index so that the element can be reused multiple times.

Combination Sum II is essentially Subset II with a target sum condition. Once you recognize the Pick / Not Pick pattern and know when to skip duplicates, the problem becomes much easier to visualize.