Generate All Combinations Sum K in DSA Java - Execution Trace

Concept Flow - Generate All Combinations Sum K

Start with empty combination

↓

Choose next number from candidates

↓

Add number to current combination

↓

Check sum of combination

↓

Recurse

↓

Backtrack: remove last number

↓

Try next number

↓

Repeat until all numbers tried

Start with an empty list, pick numbers one by one, add to current list, check sum. If sum less than K, continue; if equal, save; if more, backtrack and try next.

Execution Sample

DSA Java

void backtrack(int start, int k, List<Integer> comb, List<List<Integer>> res) {
  if (k == 0) res.add(new ArrayList<>(comb));
  for (int i = start; i <= 9; i++) {
    if (i > k) break;
    comb.add(i);
    backtrack(i + 1, k - i, comb, res);
    comb.remove(comb.size() - 1);
  }
}

This code finds all combinations of numbers 1 to 9 that sum to k without repeats.

Execution Table

Step	Operation	Current Combination	Remaining Sum (k)	Action	Visual State
1	Start backtrack(1, 3, [], [])	[]	3	Begin search	[]
2	Choose 1	[1]	2	Add 1 to combination	[1]
3	Recurse backtrack(2, 2, [1], [])	[1]	2	Continue with next numbers	[1]
4	Choose 2	[1,2]	0	Add 2, sum reached	[1,2]
5	Save combination	[1,2]	0	Add [1,2] to results	[1,2]
6	Backtrack	[1]	2	Remove last number 2	[1]
7	i=3 > 2, break	[1]	2	No more numbers, end inner loop	[1]
8	Backtrack	[]	3	Remove 1	[]
9	Choose 2	[2]	1	Add 2	[2]
10	Recurse backtrack(3, 1, [2], [[1,2]])	[2]	1	Continue	[2]
11	i=3 > 1, break	[2]	1	No more numbers possible	[2]
12	Backtrack	[]	3	Remove 2	[]
13	Choose 3	[3]	0	Add 3, sum reached	[3]
14	Save combination	[3]	0	Add [3] to results	[3]
15	Backtrack	[]	3	Remove 3	[]
16	i=4 > 3, break	[]	3	No more numbers	[]
17	End	[]	3	All options tried	[]

💡 All numbers from 1 to 9 tried or sum exceeded, recursion ends.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 9	After Step 13	After Step 14	Final
combination	[]	[1]	[1,2]	[1]	[]	[2]	[3]	[3]	[]
remaining sum (k)	3	2	0	2	3	1	0	0	3
results	[]	[]	[[1,2]]	[[1,2]]	[[1,2]]	[[1,2]]	[[1,2]]	[[1,2],[3]]	[[1,2],[3]]

Key Moments - 3 Insights

Why do we backtrack by removing the last number after recursion?

Because after exploring combinations including that number (see Step 5 and Step 6), we must remove it to try other numbers (Step 9). This ensures all combinations are explored.

Why do we break the loop when i > remaining sum?

When i > k (Steps 7 and 11), it means adding i or larger would exceed the target sum, so we stop the loop early. This saves time and avoids invalid combinations.

How do we avoid repeating the same numbers in different orders?

We always pick numbers starting from the next index (see 'start' parameter in recursion). This ensures combinations like [1,2] and [2,1] are not both generated.

Visual Quiz - 3 Questions

Look at the execution table at Step 4. What is the current combination and remaining sum?

A [2,3], -2

B [1,3], -1

C [1,2], 0

D [3], 0

💡 Hint

Check the 'Current Combination' and 'Remaining Sum (k)' columns at Step 4 in the execution_table.

At which step does the algorithm save the combination [3]?

A Step 14

B Step 13

C Step 15

D Step 16

💡 Hint

Look for the 'Save combination' action in the execution_table.

If we change the target sum k to 4, how would the visual state at Step 2 change?

A Combination would be [2], remaining sum 2

B Combination would be [1], remaining sum 3

C Combination would be [1], remaining sum 2

D Combination would be [] with remaining sum 4

💡 Hint

At Step 2, the combination is [1] and remaining sum is k - 1. If k changes to 4, remaining sum is 4 - 1 = 3.

Concept Snapshot

Generate all combinations of numbers 1-9 that sum to K.
Use backtracking: pick a number, add to current list, reduce sum.
If sum == 0, save combination.
If sum < 0, backtrack.
Move forward to avoid duplicates.
Remove last number to try new paths.

Full Transcript

This concept shows how to find all combinations of numbers from 1 to 9 that add up to a target sum K. We start with an empty list and pick numbers one by one. Each time we add a number, we reduce the remaining sum. If the sum reaches zero, we save the current combination. If it goes below zero, we stop exploring that path. We use backtracking to remove the last number and try other numbers. This way, we explore all possible combinations without repeats. The execution table traces each step, showing the current combination, remaining sum, and actions taken. Key moments clarify why we backtrack and how we avoid duplicates. The visual quiz tests understanding of the steps and changes if the target sum changes.

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