Igor Perić

Source: https://leetcode.com/problems/combination-sum/

Problem statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 500

Solution

Since there are only 30 numbers and the target < 500, a simple backtracking solution will work well here.

We define a function to keep track of the current index we are at and the current sum we have accumulated. There are two global states – one to keep track of the current set of numbers making up the sum we currently have (current_vec), and an array containing copies of all of the arrays which are confirmed to be solutions (sol).

At each step of the recursion we will try two things:

1. simply skip the number at the current index, keeping the sum intact and increasing the index
2. add the current number to the solution (if it doesn’t exceed the target sum), increasing the sum and leaving the index intact

This way we will be picking the the same number multiple times, as expected by the problem definition.

There are two exit conditions: reaching the sum and reaching the end of the candidate numbers. When we reach the target sum we will copy the current_vec array of the tracked numbers as a separate solution into the sol array, so it can be printed out later.

We start the search from index 0 and sum 0, allowing it to skip the first element if needed.

Side note: this is my first solution on Leetcode implemented in Rust. 🙂 Personally, I don’t like the fact I had to inject references to targ, current_vec and sol into a function signature and I hope I’ll learn a better way to this in the near future.

impl Solution {
    
    pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut sol: Vec<Vec<i32>> = vec![];
        let mut current_vec: Vec<i32> = vec![];
        
        fn f(idx: usize, sum: i32, cand: &Vec<i32>, targ: &i32, current_vec: &mut Vec<i32>, sol: &mut Vec<Vec<i32>>) {
            // reached the sum
            if sum == *targ {
                sol.push(current_vec.clone());
                return
            }
            
            // reached the end
            if idx == cand.len() {
                return
            }
            
            f(idx + 1, sum, cand, targ, current_vec, sol);
            
            if (sum + cand[idx] <= *targ) {
                current_vec.push(cand[idx]);
                f(idx, sum + cand[idx], cand, targ, current_vec, sol);
                current_vec.remove(current_vec.len() - 1);
            }
            
        };
        
        f(0, 0, &candidates, &target, &mut current_vec, &mut sol);
        
        sol
    }
}