LeeCode Combination Sum 更新动态规划法 - 靖空间 - CSDN博客

LeeCode Combination Sum 更新动态规划法 - 靖空间 - CSDN博客

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3] 

 

Because it is not confined to a specific length of the answers, so we cannot kown that before testing, which means there are not fixed end point of the backtracking.

We have to prun(剪枝） the branch(分支）, and backtrack to the last number.

It work like this:

1 We sort the numbers in non-descendant way

排序

2 Add the smallest number first, and loop to add it again, and again, until we find a solution, or the solution's value is larger than our target number.

迭代或递归求解

3 We backtrack, by pop up the number , to the last number.

回溯

4 and then we try the next number in candidates, loop to 2.

The key thoughts to modle the solution are: 

1 we use pushing number in and popping out to stand for backtracking thought.

回溯思想由push和pop体现

2 How many numbers in our solution stand for how deep level we iterate or recur.

3 we stop further iterate or recur by compare the number value in solution to the target number.

4 and further more, by knowing the way we arrange our candidates in a non-desendant way, we know if the current number won't fit for the answer, that the rest of the number in candidates won't fit too, so we don't need to try the rest. That's also the thought popular in AI, which call Heuristic Searching.

经验剪枝法

How we deal with repeated answers?

We just forward trying, don't look back the numbers in candiates.

At first, I was wondering whether we can do it in a iterative(迭代循环）way.

So I try, and it work. Below is my iterative program:

Read full article from LeeCode Combination Sum 更新动态规划法 - 靖空间 - CSDN博客