DAY 16 : Deep Dive into Subsets and Combination Sum Problems | My DSA Journey - Recursion

---

Introduction

Welcome to Day 16 of my DSA Journey!
For the past few weeks, I’ve been focusing on one of the most fundamental and important concepts in DSA — Recursion.

Solved some medium level questions of Subsequence which helps me to understand how subsequence concepts can be applied to solve different combination problems.

I’m documenting my journey in public to stay consistent and to help others who are also learning DSA from scratch.

Here’s what I learnt in last 3 days:

• Day 13:
  → Subsets II
  -> Combination Sum

• Day 14:
  → Combination Sum II

• Day 15:
  → Combination Sum III

Let’s break down each of these topics below 👇

---

Q 1. Subsets II:

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets, and each subset must be in non-descending order.

Example:

Input: nums = [1, 2, 2]
Total Possible Subsets: [], [1], [2], [1, 2], [2, 2], [1, 2, 2], [1, 2], [2]
But It contains duplicate elements (2 appears twice), so some subsets repeat.
We need to eliminate duplicate subsets like [1, 2] and [2] appearing more than once.
Final Output (Unique Subsets):
[ [], [1], [1, 2], [1, 2, 2], [2], [2, 2] ]

Approach:

To generate all unique subsets (power set) from a list that may contain duplicates:

1. Sort the Array

• Sorting brings duplicates together so we can skip them easily.

2. Use Backtracking (Recursion)

• Start with an empty subset.

• At each step, decide whether to include the current element.

• Skip over duplicates using the condition:

  if (i > index && arr[i] == arr[i - 1]) continue;

Recursive Tree Visualization:

Here's a visual representation of how recursion explores the subsets for [1,2,2]:

                           []
                        /      \
                    [1]        [2]
                   /   \         \
              [1,2]   [1]       [2,2]
              /                  \
          [1,2,2]                []

• Start with an empty subset []

• Add 1, then 2, then another 2 → [1,2,2]

• Backtrack and skip the duplicate 2

• Do similar for subsets starting directly with 2

The check if (i > index && arr[i] == arr[i - 1]) continue; helps skip duplicates at the same recursive level.

Code:

public static void main(String[] args) {
    int[] arr = {1, 2, 2};

    Arrays.sort(arr); // Sort to handle duplicates
    List<List<Integer>> ans = new ArrayList<>();
    subset(new ArrayList<>(), arr, 0, ans);
    System.out.println(ans);
}

static void subset(List<Integer> list, int[] arr, int index, List<List<Integer>> ans) {
    ans.add(new ArrayList<>(list)); // Add current subset

    for (int i = index; i < arr.length; i++) {
        // Skip duplicate elements on the same level
        if (i > index && arr[i] == arr[i - 1]) continue;

        list.add(arr[i]); // Include current element
        subset(list, arr, i + 1, ans); // Recursive call
        list.removeLast(); // Backtrack
    }
}

---

Q 2. Combination Sum:

Given an array of positive integers (with no duplicates) and a target sum, return all unique combinations where the chosen numbers sum up to the target.
We can use the same number an unlimited number of times. The order of numbers in the combinations does not matter.

Example:

Input: arr = [2, 3, 6, 7], target = 7

All Possible Combinations That Sum to 7:
[
[2, 2, 3],
[7]
]

• [2, 2, 3] sums to 7, Here 2 is used multiple times

• [7] sums to 7

Approach:

We solve this problem using backtracking (recursion):

1. We explore two options at each step:

   • Pick the current element and stay at the same index (since repetition is allowed).

   • Skip the current element and move to the next index.

2. If at any point the target becomes 0, it means the current list forms a valid combination, and we store a copy of it.

3. We terminate recursion when the index reaches the end of the array.

Recursive Tree Visualization:

Input: arr = [2, 3, 6, 7], target = 7

Here's how the recursive decisions look for the first few levels:

combinationSum([], 0, 7)
├── pick 2 → combinationSum([2], 0, 5)
│   ├── pick 2 → combinationSum([2,2], 0, 3)
│   │   ├── pick 2 → combinationSum([2,2,2], 0, 1)
│   │   │   └── skip to 1 → ...
│   │   └── skip to 1 → combinationSum([2,2], 1, 3)
│   │       ├── pick 3 → combinationSum([2,2,3], 1, 0) ✅
│   │       └── skip 3 → ...
│   └── skip to 1 → ...
├── pick 3 → combinationSum([3], 1, 4)
│   ├── pick 3 → combinationSum([3,3], 1, 1)
│   └── skip to 2 → ...
├── pick 6 → ...
├── pick 7 → combinationSum([7], 3, 0) ✅
└── skip 7 → ...

✅ At each point where target == 0, we store that combination.

Code:

static void combinationSum(List<Integer> list, int[] arr, int index, int target, List<List<Integer>> ans) {
    if (index == arr.length) {
        if (target == 0) {
            ans.add(new ArrayList<>(list)); // Found valid combination
        }
        return;
    }

    // Pick current element if it doesn't exceed target
    if (arr[index] <= target) {
        list.add(arr[index]);
        combinationSum(list, arr, index, target - arr[index], ans);
        list.removeLast(); // backtrack
    }

    // Skip current element
    combinationSum(list, arr, index + 1, target, ans);
}

---

Q 3. Combination Sum II:

Given a collection of candidates (which may contain duplicates) and a target number, 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.

The solution set must not contain duplicate combinations.

Example:

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

Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
All the combinations add up to the target 8, and no duplicate combinations are present.

Approach:

We use backtracking with the following strategies:

1. Sort the input array so duplicates can be skipped easily.

2. Loop from current index to end of array and:

   • Skip duplicates: If arr[i] == arr[i-1] and i > index, continue.

   • Break the loop if arr[i] > target (early stopping).

   • Pick arr[i], reduce the target, and call recursion with i + 1 (since we cannot reuse the same element).

   • After the recursive call, backtrack by removing the last element.

3. If target == 0, we have found a valid combination.

Recursive Tree Visualization:

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

[]
├── [1] → target=5
│   ├── [1,1] → target=4
│   │   └── [1,1,2] → target=2
│   │       └── [1,1,2,5] → target=-3 ❌
│   ├── [1,2] → target=2
│   │   └── [1,2,5] → target=-3 ❌
│   └── [1,5] → target=0 ✅
├── [2] → target=4
│   └── [2,5] → target=-1 ❌
└── [5] → target=1 ❌

[1,5] is the only valid combination.

Code:

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 5};
        int target = 6;

        Arrays.sort(arr);
        List<List<Integer>> ans = new ArrayList<>();
        combinationSum2(new ArrayList<>(), arr, 0, target, ans);

        System.out.println(ans);
    }

    static void combinationSum2(List<Integer> list, int[] arr, int index, int target, List<List<Integer>> ans) {
        if (target == 0) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < arr.length; i++) {
            if (i > index && arr[i] == arr[i - 1]) continue;  // Skip duplicates

            if (arr[i] > target) break;  // No need to proceed further

            list.add(arr[i]);
            combinationSum2(list, arr, i + 1, target - arr[i], ans);
            list.remove(list.size() - 1);  // Backtrack
        }
    }
}

Key Takeaways:

• Sorting is important to easily skip duplicates.

• Always check for i > index && arr[i] == arr[i - 1] to skip repeated elements.

• The array is traversed linearly, so no element is reused.

• Backtracking and careful pruning help to reduce time and avoid duplicate results.

---

Q 4. Combination Sum III:

Find all valid combinations of k numbers that add up to a number n, using only numbers from 1 to 9.
Each number can be used only once, and the combinations should be unique.

Constraints:

• Only numbers from 1 to 9 can be used.

• Each number can appear only once.

• You need exactly k numbers in each combination.

• Return only unique combinations.

Example:

Input: k = 3, n = 9
We need all combinations of 3 numbers from 1 to 9 such that their sum is 9.

Output:
[
[1, 2, 6],
[1, 3, 5],
[2, 3, 4]
]

Approach:

We use backtracking (recursion + backtrack) to explore possible number combinations:

1. Start from number 1 to 9.

2. At each step:

   • Add current number to the combination list.

   • Reduce the target by current number.

   • Move to the next number (i + 1) to avoid reuse.

3. If:

   • The list has k elements and target is 0, it is a valid combination → add it to the result.

   • The list exceeds size k or target becomes negative, backtrack.

Code:

public class CombinationSumIII {
    public static void main(String[] args) {
        int target = 9;
        int k = 3;

        List<List<Integer>> ans = new ArrayList<>();
        combinationSum3(1, new ArrayList<>(), target, k, ans);
        System.out.println(ans);
    }

    static void combinationSum3(int start, List<Integer> list, int target, int k, List<List<Integer>> ans) {
        if (list.size() == k && target == 0) {
            ans.add(new ArrayList<>(list));
            return;
        }

        if (list.size() > k || target < 0) {
            return;
        }

        for (int i = start; i <= 9; i++) {
            list.add(i);
            combinationSum3(i + 1, list, target - i, k, ans);
            list.removeLast(); // backtrack
        }
    }
}

Key Takeaways:

• Numbers 1 to 9 are used once only.

• Backtracking helps explore each combination.

• Prune branches early when:

  • list.size() > k

  • target < 0

• Use i + 1 in recursion to avoid reusing elements.

---

What's next:

I’m continuing this journey and will be:

• Posting blogs every 3 days.

• Also learning Web Development — check out my Web Dev Journey Blog.

• You can follow my journey on X (Twitter) where I post regular updates.

---

Conclusion:

In this blog of my dsa journey, I explored four foundational backtracking problems—Subset II, Combination Sum, Combination Sum II, and Combination Sum III. These problems are essential for building a strong grasp of recursion and backtracking techniques in DSA.

Here’s a quick recap of what I learned:

• Subset II taught me how to handle duplicate elements while generating all unique subsets.

• Combination Sum helped me understand how to reuse elements and explore different paths toward a target.

• Combination Sum II introduced me to pruning and duplicate-skipping for unique combinations.

• Combination Sum III challenged me with constraints on both the number of elements and their sum, enhancing our control over recursion depth.

These problems strengthen my logical thinking, recursion flow, and backtracking structure—skills that are extremely valuable for tackling real coding interviews.

If you're also starting your DSA journey, I hope this blog helps you understand recursion better. Keep learning and keep coding!

If you're on a similar journey, feel free to reach out or follow along — we’re all in this together.