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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of generating combinations summing to K

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

DSA Rust

fn generate_combinations_sum_k(n: i32, k: i32) -> Vec<Vec<i32>> {
    fn backtrack(start: i32, k: i32, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
        if k == 0 {
            res.push(path.clone());
            return;
        }
        for i in start..=4 {
            if i > k {
                break;
            }
            path.push(i);
            backtrack(i + 1, k - i, path, res);
            path.pop();
        }
    }
    let mut res = Vec::new();
    let mut path = Vec::new();
    backtrack(1, k, &mut path, &mut res);
    res
}

fn main() {
    let result = generate_combinations_sum_k(4, 5);
    println!("{:?}", result);
}

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

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

C [[5]]

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

💡 Hint

Think about combinations of unique numbers from 1 to 4 that add up to 5.

The code generates all unique combinations of numbers from 1 to 4 that sum to 5 without repetition. The valid combinations are [1,4] and [2,3].

🧠 Conceptual

intermediate

Number of combinations summing to K

How many unique combinations of numbers from 1 to 5 sum to 7?

A 6

B 5

C 7

D 8

💡 Hint

Try to list all combinations or think about subsets of {1,2,3,4,5} that sum to 7.

The unique combinations are [2,5], [3,4], [1,2,4], [1,3,3] (invalid since 3 repeats), [1,6] (6 not in range), so valid are [2,5], [3,4], [1,2,4]. The valid unique combinations are 6 in total.

🔧 Debug

advanced

Identify the error in combination sum code

What error will the following Rust code produce when generating combinations summing to 4? fn generate_combinations(k: i32) -> Vec> { let mut res = Vec::new(); let mut path = Vec::new(); fn backtrack(start: i32, k: i32, path: &mut Vec, res: &mut Vec>) { if k == 0 { res.push(path.clone()); return; } for i in start..=4 { if i > k { break; } path.push(i); backtrack(i, k - i, path, res); path.pop(); } } backtrack(1, k, &mut path, &mut res); res }

A Compilation error: missing semicolon

B Empty result vector

C Stack overflow due to infinite recursion

D Runtime panic: index out of bounds

💡 Hint

Look at the recursive call's start parameter.

The recursive call uses 'backtrack(i, ...)' instead of 'backtrack(i + 1, ...)'. This causes the same number to be reused infinitely, leading to infinite recursion and stack overflow.

📝 Syntax

advanced

Identify the syntax error in combination sum code

Which option contains the correct Rust syntax to define a backtracking function that generates combinations summing to k?

A fn backtrack(start i32, k i32, path &mut Vec<i32>, res &mut Vec<Vec<i32>>) { ... }

B fn backtrack(start: i32, k: i32, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) { ... }

C fn backtrack(start: i32, k: i32, path: Vec<i32>, res: Vec<Vec<i32>>) { ... }

D fn backtrack(start: i32, k: i32, path: &Vec<i32>, res: &Vec<Vec<i32>>) { ... }

💡 Hint

Check parameter types and mutability.

Option B correctly uses colons to specify types and mutable references for path and res. Option B misses colons. Option B passes vectors by value, which is inefficient and incorrect for backtracking. Option B uses immutable references, so path.pop() would fail.

🚀 Application

expert

Find all combinations summing to K with duplicates allowed

Given the numbers [2,3,6,7], which option shows all unique combinations where numbers can be chosen multiple times to sum to 7?

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

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

C [[7],[3,3,3]]

D [[2,2,3],[3,4]]

💡 Hint

Numbers can be reused, but combinations must be unique and sum to 7.

The valid combinations are [7] and [2,2,3]. Option A includes [2,3,3] which sums to 8, option A includes [3,3,3] which sums to 9, and option A includes 4 which is not in the list.

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 groups of numbers without regard to order, and each number can be used once or multiple times depending on problem rules.

3. Final Answer:

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

4. Quick Check:

   Combinations sum K = unique sets summing to K [OK]

Hint: Focus on sums equal to K, not products or counts [OK]

Common Mistakes:

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

2. Which Rust syntax correctly defines a function header to generate combinations summing to k with candidates as a slice of integers?

easy

A. fn combination_sum(candidates: Vec<i32>, k: i32) -> Vec<i32>

B. fn combination_sum(candidates: Vec<i32>, k: i32) -> i32

C. fn combination_sum(candidates: &[i32], k: i32) -> i32

D. fn combination_sum(candidates: &[i32], k: i32) -> Vec

Solution

1. Step 1: Identify input types

   The candidates are passed as a slice reference &[i32] to avoid ownership issues and allow read-only access.

2. Step 2: Identify return type

   The function returns a vector of vectors of i32, representing all combinations found.

3. Final Answer:

   fn combination_sum(candidates: &[i32], k: i32) -> Vec -> Option D

4. Quick Check:

   Function signature with slice input and Vec output [OK]

Hint: Use &[i32] for input slice and Vec for combinations [OK]

Common Mistakes:

• Returning i32 instead of combinations
• Using Vec<i32> input causing ownership issues
• Wrong return type for multiple combinations

3. What is the output of this Rust code snippet?

fn main() {
    let candidates = vec![2, 3, 6, 7];
    let target = 7;
    let result = combination_sum(&candidates, target);
    println!("{:?}", result);
}

fn combination_sum(candidates: &[i32], target: i32) -> Vec {
    fn backtrack(start: usize, target: i32, path: &mut Vec<i32>, res: &mut Vec, candidates: &[i32]) {
        if target == 0 {
            res.push(path.clone());
            return;
        }
        for i in start..candidates.len() {
            if candidates[i] > target {
                continue;
            }
            path.push(candidates[i]);
            backtrack(i, target - candidates[i], path, res, candidates);
            path.pop();
        }
    }
    let mut res = vec![];
    let mut path = vec![];
    backtrack(0, target, &mut path, &mut res, candidates);
    res
}

medium

A. [[3, 3, 3], [7]]

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

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

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

Solution

1. Step 1: Understand backtracking logic

   The function tries combinations starting from each candidate, allowing repeats, and collects those summing to target 7.

2. Step 2: Trace valid combinations

   Valid combinations are [2, 2, 3] (2+2+3=7) and [7] itself.

3. Final Answer:

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

4. Quick Check:

   Backtracking finds combinations summing to 7 [OK]

Hint: Check sums carefully; 2+2+3 and 7 match target [OK]

Common Mistakes:

• Including invalid sums like 2+3+6
• Ignoring repeated use of candidates
• Missing single element combination [7]

4. Identify the bug in this Rust function for generating combinations summing to k:

fn combination_sum(candidates: &[i32], target: i32) -> Vec {
    fn backtrack(start: usize, target: i32, path: &mut Vec<i32>, res: &mut Vec, candidates: &[i32]) {
        if target == 0 {
            res.push(path.clone());
            return;
        }
        for i in start..candidates.len() {
            if candidates[i] >= target {
                continue;
            }
            path.push(candidates[i]);
            backtrack(i, target - candidates[i], path, res, candidates);
            path.pop();
        }
    }
    let mut res = vec![];
    let mut path = vec![];
    backtrack(0, target, &mut path, &mut res, candidates);
    res
}

medium

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

B. The condition should be candidates[i] > target, not >= target

C. The path vector should not be cloned when pushing to res

D. The function should return i32 instead of Vec

Solution

1. Step 1: Analyze the pruning condition

   The condition 'if candidates[i] >= target' skips candidates equal to target, missing valid combinations like [target] itself.

2. Step 2: Correct the condition

   Changing to 'candidates[i] > target' allows candidates equal to target to be included, fixing the bug.

3. Final Answer:

   The condition should be candidates[i] > target, not >= target -> Option B

4. Quick Check:

   Pruning must allow candidates equal to target [OK]

Hint: Use >, not >=, to include candidates equal to target [OK]

Common Mistakes:

• Skipping candidates equal to target
• Incorrect recursive index causing duplicates
• Not cloning path before pushing

5. Given candidates = [1, 2, 3] and target = 4, which of the following is the correct set of all unique combinations summing to 4, assuming candidates can be used unlimited times?

hard

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

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

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

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

Solution

1. Step 1: List all combinations summing to 4

   Possible combinations using unlimited candidates are [1,1,1,1], [1,1,2], [1,3], and [2,2].

2. Step 2: Check for duplicates and invalid entries

   [3,1] is a duplicate of [1,3] (order doesn't matter), and [4] is invalid as 4 is not in candidates.

3. Final Answer:

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

4. Quick Check:

   Unique combinations without duplicates or invalid numbers [OK]

Hint: Exclude duplicates and numbers not in candidates [OK]

Common Mistakes:

• Including duplicates with different order
• Adding numbers not in candidates
• Missing valid combinations