039 Combination Sum

#lcmedium#backtracking#leetcode

Problem Link

Solution §

Basically, treat each ‘candidate’ as a branch, and we may use these candidates a infinite number of times.

As a result, each ‘branch’ is $Target-Candidate$. We need to keep track of the candidates we used by having a ‘path’ vector. We can add a candidate to the path vector, recurse down, then once all is said and done, can pop the candidate (we are done exploring).

We sort input array to properly recurse, and to avoid duplicate paths.

For any given path, we will never branch lower than it’s current maximum candidate. I.E. For path P, $max(|P|)=c$, we will only explore children: $c^{\prime }\ge c$.

• This is to avoid duplicates.
  • Example: $[2,3]$ Target: 7
  • $[2,2,3]=[2,3,2]=[3,2,2]$
  • If we ONLY take branches $\ge$ max, $[2,2,3]$ is the only answer.

Scratch §

Sort input. Run subproblem: Target - K

Brute Force: Explore every branch, if the branch leads to 0, append to output.

Example: candidates = [2,3,6,7], target = 7

Problem: How to keep track of path? Can locally maintain a vector of ‘path’

Works!