## Leetcode 39 – Combination Sum

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 = 7Output:[[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 = 8Output:[[2,2,2,2],[2,3,3],[3,5]]

**Example 3:**

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

**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:

- simply skip the number at the current index, keeping the sum intact and
**increasing the index** - 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 } }