Combination Sum: A Recursion Pattern Where Elements Can Be Taken More Than Once

Introduction

In recursion-based problem-solving, certain patterns appear frequently. One such pattern is used in Combination Sum, where we can take an element more than once in a recursive call. Understanding this pattern is crucial for solving many combinatorial problems efficiently.

In this blog, we'll break down the Combination Sum recursion pattern, its characteristics, and how it differs from other backtracking approaches.

---

The Core Idea of the Combination Sum Pattern

The fundamental principle behind the Combination Sum recursion pattern is:

1. Elements can be picked multiple times – Unlike permutations or subset problems where elements are picked once, here we can reuse elements.
2. DFS (Depth-First Search) style recursion – The function explores possible combinations recursively.
3. Backtracking – We explore an option, make a recursive call, and backtrack to try other possibilities.
4. Pruning – If the target becomes negative, we stop further exploration.

---

Code Example

Below is the Java implementation of Combination Sum, showcasing this pattern:

import java.util.*;

public class CombinationSum {
    public static void combinationSum(int[] candidates, int target, int start, List<Integer> temp, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = start; i < candidates.length; i++) { // Loop through elements
            if (target >= candidates[i]) {
                temp.add(candidates[i]); // Pick the element
                combinationSum(candidates, target - candidates[i], i, temp, result); // Recursive call allowing repetition
                temp.remove(temp.size() - 1); // Backtrack
            }
        }
    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> result = new ArrayList<>();
        combinationSum(candidates, target, 0, new ArrayList<>(), result);
        System.out.println(result); // Output: [[2,2,3], [7]]
    }
}

---

Recursion Tree Breakdown

Let’s analyze the recursion tree for candidates = [2, 3, 6, 7] and target = 7.

combinationSum(7, 0, [])
├── 2 added → combinationSum(5, 0, [2])
│   ├── 2 added → combinationSum(3, 0, [2, 2])
│   │   ├── 2 added → combinationSum(1, 0, [2, 2, 2]) ❌ (Invalid, target < 2)
│   │   ├── 3 added → combinationSum(0, 1, [2, 2, 3]) ✅ (Valid, add to result)
│   ├── 3 added → combinationSum(2, 1, [2, 3]) ❌ (Invalid)
│   ├── 6 skipped
│   ├── 7 skipped
├── 3 added → combinationSum(4, 1, [3])
│   ├── 3 added → combinationSum(1, 1, [3, 3]) ❌ (Invalid)
│   ├── 6 skipped
│   ├── 7 skipped
├── 6 added → combinationSum(1, 2, [6]) ❌ (Invalid)
├── 7 added → combinationSum(0, 3, [7]) ✅ (Valid, add to result)

Result:

[[2, 2, 3], [7]]

---

Key Takeaways

🔹 1. Elements Can Be Used Multiple Times

Unlike subset or permutation problems, here we pass i (not i+1) in recursion, allowing the same element to be used multiple times.

🔹 2. Backtracking Ensures Correct Combinations

We remove the last added element (temp.remove(temp.size() - 1)) before moving to the next candidate.

🔹 3. Stopping Condition Prevents Invalid Cases

If target == 0, we add the combination to results. If target < 0, we return immediately.

🔹 4. Optimization with Sorting (Optional)

Sorting candidates before recursion can help optimize the search by breaking early.

---

Subset Sum: A Variation Where Elements Can Be Used Only Once

If we modify the Combination Sum problem so that each element can be used only once, then it essentially becomes a Subset Sum or Combination Sum II problem.

Key Differences Between "Combination Sum" and "Subset Sum"

Feature	Combination Sum (Repeated Elements)	Subset Sum (Unique Elements)
Element Reuse	Allowed (pass i)	Not allowed (pass i+1)
Recursion Parameter	combinationSum(target - candidates[i], i, ...)	combinationSum(target - candidates[i], i + 1, ...)
Duplicate Combinations	Prevented by keeping i same	Prevented by skipping used elements

Implementation for Unique Elements (Subset Sum)

public static void combinationSumUnique(int[] candidates, int target, int start, List<Integer> temp, List<List<Integer>> result) {
    if (target == 0) {
        result.add(new ArrayList<>(temp));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) continue; // Skip duplicates
        if (target >= candidates[i]) {
            temp.add(candidates[i]); // Pick element
            combinationSumUnique(candidates, target - candidates[i], i + 1, temp, result); // Move to i+1 to avoid reuse
            temp.remove(temp.size() - 1); // Backtrack
        }
    }
}

---

Permutations: When Order Matters

In permutations, order matters, unlike combinations.

Permutation Code (Without Duplicates)

public static void permute(int[] nums, int index, List<List<Integer>> result) {
    if (index == nums.length) {
        result.add(new ArrayList<>(Arrays.asList(nums.clone())));
        return;
    }
    for (int i = index; i < nums.length; i++) {
        swap(nums, index, i);
        permute(nums, index + 1, result);
        swap(nums, index, i); // Backtrack
    }
}

By mastering these patterns—Combination Sum, Subset Sum, and Permutations—you can solve many recursion and backtracking problems efficiently! 🚀

Happy Coding! 😊