Generate All Combinations Sum K in DSA Java

Mental Model

Find all groups of numbers from a list that add up exactly to a target number by trying each number and exploring further choices.

Analogy: Imagine you have a box of different colored beads and want to pick some beads so their total weight is exactly a certain number. You try picking one bead, then another, and so on, backtracking if the total weight goes over or you run out of beads.

Candidates: [2, 3, 6, 7]
Target: 7
Start -> [] (empty combination)
Try 2 -> [2]
Try 2 again -> [2 -> 2]
Try 3 -> [2 -> 2 -> 3]
Backtrack when sum > 7

Dry Run Walkthrough

Input: candidates: [2, 3, 6, 7], target: 7

Goal: Find all combinations of candidates that sum to 7

Step 1: Start with empty combination [] and target 7

[] (sum=0, target=7)

Why: We begin with no numbers chosen and full target to reach

Step 2: Pick 2, combination becomes [2], target reduces to 5

[2] (sum=2, target=5)

Why: Try including 2 to reach target

Step 3: Pick 2 again, combination [2, 2], target 3

[2 -> 2] (sum=4, target=3)

Why: We can reuse numbers, try 2 again

Step 4: Pick 3, combination [2, 2, 3], target 0 (found valid)

[2 -> 2 -> 3] (sum=7, target=0)

Why: Sum matches target, save this combination

Step 5: Backtrack: remove last 3, try next candidate 6 at [2, 2]

[2 -> 2] (sum=4, target=3)

Why: Try other options after backtracking

Step 6: Pick 6, sum 10 > target 7, backtrack

[2 -> 2] (sum=4, target=3)

Why: Sum exceeded target, discard this path

Step 7: Backtrack to [2], try next candidate 3

[2] (sum=2, target=5)

Why: Try other candidates after backtracking

Step 8: Pick 3, combination [2, 3], target 2

[2 -> 3] (sum=5, target=2)

Why: Try adding 3 to combination

Step 9: Pick 3 again, sum 8 > target 7, backtrack

[2 -> 3] (sum=5, target=2)

Why: Sum exceeded target, discard path

Step 10: Backtrack to [], try candidate 3

[] (sum=0, target=7)

Why: Try starting with 3

Step 11: Pick 3, combination [3], target 4

[3] (sum=3, target=4)

Why: Try adding 3

Step 12: Pick 3 again, combination [3, 3], target 1

[3 -> 3] (sum=6, target=1)

Why: Try adding 3 again

Step 13: Pick 3 again, sum 9 > target 7, backtrack

[3 -> 3] (sum=6, target=1)

Why: Sum exceeded target, discard path

Step 14: Backtrack to [], try candidate 6

[] (sum=0, target=7)

Why: Try starting with 6

Step 15: Pick 6, combination [6], target 1

[6] (sum=6, target=1)

Why: Try adding 6

Step 16: Pick 6 again, sum 12 > target 7, backtrack

[6] (sum=6, target=1)

Why: Sum exceeded target, discard path

Step 17: Backtrack to [], try candidate 7

[] (sum=0, target=7)

Why: Try starting with 7

Step 18: Pick 7, combination [7], target 0 (found valid)

[7] (sum=7, target=0)

Why: Sum matches target, save this combination

Result:

[2 -> 2 -> 3] and [7]

Annotated Code

DSA Java

import java.util.*;

public class CombinationSum {

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); // optional but helps optimization
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] candidates, int target, int start, List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current)); // found valid combination
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) {
                break; // no need to continue if candidate exceeds target
            }
            current.add(candidates[i]); // choose candidate
            backtrack(candidates, target - candidates[i], i, current, result); // explore further with updated target
            current.remove(current.size() - 1); // backtrack: remove last chosen
        }
    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> combinations = combinationSum(candidates, target);
        for (List<Integer> combo : combinations) {
            System.out.println(combo);
        }
    }

if (target == 0) {

Check if current combination sums exactly to target

result.add(new ArrayList<>(current));

Save a copy of the valid combination

if (candidates[i] > target) { break; }

Stop exploring further if candidate exceeds remaining target

current.add(candidates[i]);

Add candidate to current combination

backtrack(candidates, target - candidates[i], i, current, result);

Recurse with reduced target and same start index to allow reuse

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

Remove last candidate to backtrack and try other options

Output

[2, 2, 3]

[7]

Complexity Analysis

Time: O(N^(T/M)) where N is number of candidates, T is target, M is minimum candidate value, because we explore combinations by choosing candidates repeatedly until target is reached

Space: O(T/M) for recursion stack and current combination storage, proportional to max depth of recursion

vs Alternative: Compared to brute force checking all subsets (2^N), this backtracking prunes paths early when sum exceeds target, improving efficiency

Edge Cases

Empty candidates array

Returns empty list as no combinations possible

DSA Java

for (int i = start; i < candidates.length; i++) {

Target is zero

Returns list with empty combination as sum zero is valid

DSA Java

if (target == 0) {

Candidates contain duplicates

Duplicates allowed, combinations may include repeated numbers as per problem statement

DSA Java

backtrack(candidates, target - candidates[i], i, current, result);

When to Use This Pattern

When asked to find all combinations of numbers that sum to a target with unlimited reuse, use backtracking to explore choices and prune paths exceeding the target.

Common Mistakes

Mistake: Not backtracking by removing last chosen number after recursive call
Fix: Add current.remove(current.size() - 1) after recursion to undo choice

Mistake: Starting next recursion from i+1 instead of i, disallowing reuse
Fix: Use i as start index in recursive call to allow reuse of same candidate

Mistake: Not breaking loop when candidate exceeds target, causing unnecessary recursion
Fix: Add break when candidates[i] > target to prune search

Summary

Finds all unique combinations of numbers that sum exactly to a target using backtracking.

Use when you need to list all ways to sum to a number from given candidates with unlimited reuse.

The key is to try each candidate, recurse with reduced target, and backtrack to explore all possibilities.

Practice

1. What does the problem "Generate All Combinations Sum K" ask you to find?

easy

A. All unique combinations of numbers that add up to K

B. The largest number less than K

C. The sum of all numbers from 1 to K

D. The product of all numbers that divide K

Solution

1. Step 1: Understand the problem goal

   The problem asks to find all unique sets of numbers that add exactly to the target sum K.

2. Step 2: Clarify what combinations mean

   Combinations mean selecting numbers without caring about order, but each combination must sum to K.

3. Final Answer:

   All unique combinations of numbers that add up to K -> Option A

4. Quick Check:

   Sum of combinations = K [OK]

Hint: Focus on sums equal to K, not order or multiplication [OK]

Common Mistakes:

• Confusing combinations with permutations
• Looking for product instead of sum
• Ignoring uniqueness of combinations

2. Which of the following Java method signatures is correct for a function that generates all combinations summing to K using backtracking?

easy

A. public void findCombinations(int[] nums, int target, List<Integer> current, List result, int start)

B. public int findCombinations(int[] nums, int target)

C. void findCombinations(int target, int[] nums, List result)

D. public List<Integer> findCombinations(int target, int[] nums)

Solution

1. Step 1: Identify parameters needed for backtracking

   We need the array, target sum, current combination list, result list, and start index to avoid duplicates.

2. Step 2: Match method signature with these parameters

   public void findCombinations(int[] nums, int target, List<Integer> current, List result, int start) matches all needed parameters and returns void as it fills the result list.

3. Final Answer:

   public void findCombinations(int[] nums, int target, List<Integer> current, List result, int start) -> Option A

4. Quick Check:

   Correct parameters for backtracking method [OK]

Hint: Backtracking needs current, result lists, and start index [OK]

Common Mistakes:

• Missing start index parameter
• Wrong return type for backtracking method
• Incorrect parameter order

3. What will be the output of the following Java code snippet?

List result = new ArrayList<>();
int[] nums = {2, 3, 6, 7};
int target = 7;
findCombinations(nums, target, new ArrayList<>(), result, 0);
System.out.println(result);

Assuming findCombinations correctly finds all unique combinations summing to target.

medium

A. [[2, 3, 6], [7]]

B. [[7]]

C. [[2, 2, 3], [7]]

D. [[2, 2, 2, 3], [7]]

Solution

1. Step 1: Identify combinations that sum to 7

   From nums, 7 alone sums to 7, and 2+2+3 also sums to 7.

2. Step 2: Confirm no other combinations sum to 7

   3+6=9, 2+3+6=11, 2+2+2+3=9 (too large), so only [2,2,3] and [7] are valid.

3. Final Answer:

   [[2, 2, 3], [7]] -> Option C

4. Quick Check:

   Valid combinations sum to 7 [OK]

Hint: Check sums carefully; only valid combos appear [OK]

Common Mistakes:

• Including invalid sums
• Missing repeated elements allowed
• Confusing order of elements

4. Identify the error in this Java backtracking code snippet for generating combinations summing to K:

void findCombinations(int[] nums, int target, List<Integer> current, List result, int start) {
    if (target == 0) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = start; i < nums.length; i++) {
        if (nums[i] > target) continue;
        current.add(nums[i]);
        findCombinations(nums, target - nums[i], current, result, i);
        current.remove(current.size());
    }
}

medium

A. The recursive call should use i + 1 instead of i

B. The base case should check if target < 0 instead of target == 0

C. The loop should start from 0 instead of start

D. Removing element with current.remove(current.size()) causes IndexOutOfBoundsException

Solution

1. Step 1: Check the remove method usage

   List indices start at 0, so last element index is current.size() - 1, not current.size().

2. Step 2: Identify correct remove call

   Using current.remove(current.size()) causes IndexOutOfBoundsException because index is out of range.

3. Final Answer:

   Removing element with current.remove(current.size()) causes IndexOutOfBoundsException -> Option D

4. Quick Check:

   List remove index must be size-1 [OK]

Hint: Remove last element with index size-1, not size [OK]

Common Mistakes:

• Removing element at wrong index
• Ignoring base case correctness
• Wrong loop start index

5. Given the array nums = {1, 2, 3} and target sum 4, which of the following is the correct set of all unique combinations where numbers can be repeated and sum to 4?

hard

A. [[1,1,1,1], [1,1,2], [1,3], [2,2], [3,1]]

B. [[1,1,1,1], [1,1,2], [1,3], [2,2]]

C. [[1,1,1,1], [1,1,2], [1,3], [2,2], [4]]

D. [[1,1,1,1], [1,1,2], [2,2], [3,1]]

Solution

1. Step 1: List all combinations summing to 4 with repeats allowed

   Possible combos: [1,1,1,1], [1,1,2], [1,3], [2,2]. Note [3,1] is same as [1,3] and duplicates are not allowed.

2. Step 2: Check options for duplicates and invalid elements

   [[1,1,1,1], [1,1,2], [1,3], [2,2], [3,1]] includes [3,1] duplicate of [1,3]. [[1,1,1,1], [1,1,2], [1,3], [2,2], [4]] includes [4] which is not in nums. [[1,1,1,1], [1,1,2], [2,2], [3,1]] misses [1,3]. [[1,1,1,1], [1,1,2], [1,3], [2,2]] correctly lists unique combinations.

3. Final Answer:

   [[1,1,1,1], [1,1,2], [1,3], [2,2]] -> Option B

4. Quick Check:

   Unique combos sum to 4 without duplicates [OK]

Hint: Avoid duplicates by sorting or fixed order in combos [OK]

Common Mistakes:

• Counting duplicates as separate combinations
• Including numbers not in the array
• Ignoring repeated use of numbers