Generate All Combinations Sum K in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of combinations summing to K

What is the output of the following Java code that generates all combinations of numbers from 1 to 4 that sum to 5?

DSA Java

import java.util.*;

public class Main {
    static void findCombinations(int start, int k, int target, List<Integer> current, List<List<Integer>> result) {
        if (target == 0 && current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (target < 0 || current.size() > k) return;

        for (int i = start; i <= 4; i++) {
            current.add(i);
            findCombinations(i + 1, k, target - i, current, result);
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> result = new ArrayList<>();
        findCombinations(1, 2, 5, new ArrayList<>(), result);
        System.out.println(result);
    }
}

A [[1, 4], [2, 3]]

B [[1, 4], [2, 3], [3, 2], [4, 1]]

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

D [[5]]

💡 Hint

Think about combinations of size 2 that add up to 5 using numbers 1 to 4 without repetition.

The code finds all unique combinations of 2 numbers from 1 to 4 that sum to 5. The valid pairs are [1,4] and [2,3]. The code avoids duplicates by increasing the start index each recursion.

🧠 Conceptual

intermediate

Number of combinations of size K summing to target

Given numbers from 1 to 5, how many unique combinations of size 3 sum exactly to 7?

A 4

B 3

C 5

D 6

💡 Hint

Try listing all combinations of 3 numbers from 1 to 5 and check which sum to 7.

The valid unique combinations without repetition are [1,2,4], [1,3,3] invalid (3 repeats), [2,3,2] invalid (2 repeats), [1,5,1] invalid (1 repeats). So only [1,2,4], [1,3,3] invalid, [2,3,2] invalid. The correct valid combinations are [1,2,4], [1,3,3] invalid, [2,3,2] invalid. So answer is 4.

🔧 Debug

advanced

Identify the error in combination sum code

What error does the following Java code produce when trying to generate all combinations of size 3 summing to 6?

DSA Java

import java.util.*;

public class Main {
    static void findCombinations(int start, int k, int target, List<Integer> current, List<List<Integer>> result) {
        if (target == 0 && current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (target < 0 || current.size() > k) return;

        for (int i = start; i <= 5; i++) {
            current.add(i);
            findCombinations(i, k, target - i, current, result);
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> result = new ArrayList<>();
        findCombinations(1, 3, 6, new ArrayList<>(), result);
        System.out.println(result);
    }
}

A NullPointerException at runtime

B Infinite recursion causing StackOverflowError

C No output because base case never reached

D Compilation error due to missing semicolon

💡 Hint

Check the recursive call's start parameter and how it affects the loop.

The recursive call uses 'i' as the start parameter instead of 'i + 1', so the same number can be chosen repeatedly causing infinite recursion and eventually StackOverflowError.

📝 Syntax

advanced

Identify the syntax error in combination sum code

Which option contains the syntax error in this Java method to generate combinations?

DSA Java

void findCombinations(int start, int k, int target, List<Integer> current, List<List<Integer>> result) {
    if (target == 0 && current.size() == k) {
        result.add(new ArrayList<>(current));
        return;
    }
    if (target < 0 || current.size() > k) return;

    for (int i = start; i <= 5; i++) {
        current.add(i)
        findCombinations(i + 1, k, target - i, current, result);
        current.remove(current.size() - 1);
    }
}

A Incorrect for loop syntax

B Missing return type in method declaration

C Missing semicolon after current.add(i)

D Incorrect method call syntax

💡 Hint

Look carefully at the line with current.add(i)

The line current.add(i) is missing a semicolon at the end, causing a syntax error.

🚀 Application

expert

Find all unique combinations of size K summing to target with duplicates allowed

Given numbers from 1 to 3, which output correctly shows all unique combinations of size 3 that sum to 5 when numbers can be repeated?

DSA Java

import java.util.*;

public class Main {
    static void findCombinations(int start, int k, int target, List<Integer> current, List<List<Integer>> result) {
        if (target == 0 && current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        if (target < 0 || current.size() > k) return;

        for (int i = start; i <= 3; i++) {
            current.add(i);
            findCombinations(i, k, target - i, current, result);
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> result = new ArrayList<>();
        findCombinations(1, 3, 5, new ArrayList<>(), result);
        System.out.println(result);
    }
}

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

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

C [[1,1,3], [1,2,2], [1,3,1], [2,1,2], [2,2,1], [3,1,1]]

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

💡 Hint

Numbers can repeat and order does not matter, so combinations like [1,3,1] and [3,1,1] are considered the same if order is ignored.

The code allows repeated numbers by calling findCombinations with start = i, so numbers can be reused. The output lists unique combinations of size 3 summing to 5 without duplicates. Option D correctly lists unique combinations without duplicates.

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