# Backtracking - Combination Sum

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

DFS, Backtracking

## Problem

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

1
2
3
4
5
6

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

1
2

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

**Example 3:**

1
2

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

## Solution

I will provide two templates for solving problem like this. However let’s visualize the problem first. Every step of the way we have a decision to make. (1) whether to include current number at index `i `

or (2) not include it and move to next number at `i+1`

.

In the below diagram it’s defined as `include step`

and `skip step`

.

Now to solve problem like this we can follow two separate templates.

- In the
**template 1**, we simulate traversing the array using two recursive calls from each`dfs()`

function. One for current`index`

and another for the next`index`

. - In
**template 2**, we use a loop to traverse the array recursively for each`index`

position starting from current position.

### Basic Structure

Before implementing each solutions, let’s build the basic structure of the code, which is not going to change. We would need one variables for the `output`

to return. The `dfs()`

function takes 3 parameters :

- The
`index`

location for traversing - The
`path`

to return to. - The
`curr_sum`

whenever need to determine base case.

1
2
3

output = []
def dfs(index, path, curr_sum):

Lets also define the terminating condition when the `path`

can be added to the `output`

.

1
2
3
4

def dfs(index, path, curr_sum):
if curr_sum == target:
output.append(path.copy())
return

We will skip the internal logic and finally call the `dfs()`

and return the `output`

.

1
2
3
4
5
6
7
8
9
10
11

output = []
def dfs(index, path, curr_sum):
if curr_sum == target:
output.append(path.copy())
return
# Traversal logic goes here
def(0,[],0)
return output

### Implement using Template 1

When using **template 1**, we can’t keep incrementing the `index`

so we need to check for boundary condition. We shouldn’t traverse further if any one of the following is `True`

.

1
2

if index == len(candidates) or curr_sum > target:
return

Now it’s time to follow the building blocks of template 1. Here is the `dfs(i)`

call where we first update `path`

and add pass the same `index`

to `dfs()`

. Once done we will `pop()`

back the latest so that we now have the original `path`

to try the next `index`

.

1
2
3

path.append(candidates[index])
dfs(index,path,curr_sum+candidates[index])
path.pop()

Increase the `index`

and call the `dfs()`

using existing `path`

and `curr_sum`

1

dfs(index+1,path,curr_sum)

Thats all needed for implementing using **template 1**.

### Implement using Template 2

I feel this implementation is very easy to implement using the **Template 2**. We need to traverser using a loop till end of the `candidates`

array starting from current `index`

and call `dfs()`

only if the `curr_sum+candidates[j]<=target`

.

Append `candidates[j]`

to current `path`

, call the `dfs()`

and then backtrack `path`

.

1
2
3
4
5

for j in range(index,len(candidates)):
if curr_sum+candidates[j]<=target:
path.append(candidates[j])
dfs(j,path,curr_sum+candidates[j])
path.pop()

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def combinationSum(candidates, target):
output = []
def dfs(index, path, curr_sum):
if curr_sum == target:
output.append(path.copy())
return
'''
# Using Template 2
for j in range(index,len(candidates)):
if curr_sum+candidates[j]<=target:
path.append(candidates[j])
dfs(j,path,curr_sum+candidates[j])
path.pop()
'''
# Using Template 1
if index == len(candidates) or curr_sum > target:
return
path.append(candidates[index])
dfs(index, path, curr_sum+candidates[index])
path.pop()
dfs(index+1, path, curr_sum)
dfs(0, [], 0)
return output