Generate All Combinations Sum K in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start the recursive function call for generating combinations.

DSA Rust

fn combination_sum_k(k: usize, n: usize) -> Vec<Vec<usize>> {
    let mut result = Vec::new();
    let mut current = Vec::new();
    backtrack(1, k, n, &mut current, &mut result);
    result
}

fn backtrack(start: usize, k: usize, n: usize, current: &mut Vec<usize>, result: &mut Vec<Vec<usize>>) {
    if n == 0 && current.len() == k {
        result.push(current.clone());
        return;
    }
    if current.len() > k || n < 0 {
        return;
    }
    for i in start..=9 {
        current.push(i);
        backtrack(i + 1, k, n - i, current, result);
        current.pop();
    }
}

fn main() {
    let combinations = combination_sum_k([1], 7);
    println!("{:?}", combinations);
}

Drag options to blanks, or click blank then click option'

A2

B4

C3

D5

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong value for k in the initial call.

Confusing the sum target with the number of elements.

The function call starts with k=2 to find combinations of 2 numbers that sum to 7.

2fill in blank

medium

Complete the code to check if the current combination is valid and add it to the result.

DSA Rust

fn backtrack(start: usize, k: usize, n: usize, current: &mut Vec<usize>, result: &mut Vec<Vec<usize>>) {
    if n == 0 && current.len() == [1] {
        result.push(current.clone());
        return;
    }
    if current.len() > k || n < 0 {
        return;
    }
    for i in start..=9 {
        current.push(i);
        backtrack(i + 1, k, n - i, current, result);
        current.pop();
    }
}

Drag options to blanks, or click blank then click option'

An

Bstart

Ck

Dresult.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Checking against n instead of k.

Using start or result length incorrectly.

We check if the current combination length equals k to ensure correct size before adding.

3fill in blank

hard

Fix the error in the loop range to correctly iterate over numbers 1 to 9.

DSA Rust

for i in [1] {
    current.push(i);
    backtrack(i + 1, k, n - i, current, result);
    current.pop();
}

Drag options to blanks, or click blank then click option'

A0..9

B1..=9

Cstart..9

Dstart..=9

Attempts:

3 left

💡 Hint

Common Mistakes

Using exclusive range which excludes 9.

Starting from 1 instead of start.

Using start..=9 includes the number 9 in the loop, which is required.

4fill in blank

hard

Fill both blanks to correctly handle the base cases in the backtrack function.

DSA Rust

fn backtrack(start: usize, k: usize, n: isize, current: &mut Vec<usize>, result: &mut Vec<Vec<usize>>) {
    if n == 0 && current.len() == [1] {
        result.push(current.clone());
        return;
    }
    if current.len() > [2] || n < 0 {
        return;
    }
    for i in start..=9 {
        current.push(i);
        backtrack(i + 1, k, n - i as isize, current, result);
        current.pop();
    }
}

Drag options to blanks, or click blank then click option'

Ak

Bn

Cstart

Dresult.len()

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variables for length checks.

Confusing n with k.

Both blanks should be 'k' to check combination size correctly.

5fill in blank

hard

Fill all three blanks to correctly convert and check the remaining sum in the recursive call.

DSA Rust

for i in start..=9 {
    current.push(i);
    backtrack(i + 1, k, n [1] i as [2], current, result);
    current.pop();
}

fn backtrack(start: usize, k: usize, n: [3], current: &mut Vec<usize>, result: &mut Vec<Vec<usize>>) {
    if n == 0 && current.len() == k {
        result.push(current.clone());
        return;
    }
    if current.len() > k || n < 0 {
        return;
    }
    for i in start..=9 {
        current.push(i);
        backtrack(i + 1, k, n - i as isize, current, result);
        current.pop();
    }
}

Drag options to blanks, or click blank then click option'

A-

Bisize

Cusize

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of subtraction.

Casting to usize instead of isize.

Mismatch in n's type.

We subtract i cast to isize from n which is of type isize.

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