Generate All Combinations Sum K in DSA Rust - Build from Scratch

Generate All Combinations Sum K

📖 Scenario: Imagine you are organizing a small party and want to create different groups of friends to invite. You want to find all possible groups of a certain size where the sum of their ages equals a specific number. This helps you plan activities suitable for those age groups.

🎯 Goal: Build a Rust program that finds all combinations of numbers from a given list that add up exactly to a target sum k. Each combination should have exactly k elements.

📋 What You'll Learn

Create a vector of integers called numbers with the exact values: 2, 3, 6, 7

Create an integer variable called target_sum and set it to 7

Write a recursive function called find_combinations that finds all combinations of k numbers from numbers that sum to target_sum

Print the resulting combinations as vectors

💡 Why This Matters

🌍 Real World

Finding combinations that sum to a target is useful in budgeting, resource allocation, and planning groups or teams with specific constraints.

💼 Career

This problem teaches recursion, backtracking, and working with collections in Rust, skills valuable for software engineers working on algorithms and optimization.

1

Create the initial data vector

Create a vector called numbers with the exact integers 2, 3, 6, and 7.

DSA Rust

# Create the vector numbers with values 2, 3, 6, 7
# Your code here

Hint

Use let numbers = vec![2, 3, 6, 7]; to create the vector.

2

Add the target sum variable

Add an integer variable called target_sum and set it to 7 inside the main function after the numbers vector.

DSA Rust

fn main() {
    let numbers = vec![2, 3, 6, 7];
    // Create target_sum variable and set to 7
    // Your code here
}

Hint

Use let target_sum = 7; to create the variable.

3

Write the recursive function to find combinations

Write a recursive function called find_combinations with parameters numbers: &Vec<i32>, target: i32, start: usize, current: &mut Vec<i32>, and results: &mut Vec<Vec<i32>>. The function should find all combinations of numbers starting from index start that sum to target. Add valid combinations to results. Call this function inside main with appropriate arguments to find all combinations that sum to target_sum.

DSA Rust

fn main() {
    let numbers = vec![2, 3, 6, 7];
    let target_sum = 7;

    // Define find_combinations function below
    // Your code here
}

Hint

Use recursion to explore each number starting from start. Add numbers to current and subtract from target. When target is zero, add current to results.

4

Print the resulting combinations

Add code inside main to print the results vector after calling find_combinations. This will display all combinations that sum to target_sum.

DSA Rust

fn find_combinations(numbers: &Vec, target: i32, start: usize, current: &mut Vec, results: &mut Vec>) {
    if target == 0 {
        results.push(current.clone());
        return;
    }
    if target < 0 {
        return;
    }
    for i in start..numbers.len() {
        current.push(numbers[i]);
        find_combinations(numbers, target - numbers[i], i + 1, current, results);
        current.pop();
    }
}

fn main() {
    let numbers = vec![2, 3, 6, 7];
    let target_sum = 7;
    let mut results = Vec::new();
    let mut current = Vec::new();
    find_combinations(&numbers, target_sum, 0, &mut current, &mut results);
    // Print results below
    // Your code here
}

Hint

Use a for loop to print each combination vector in results.

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