Tag name:DFS

[LeetCode] Combination Sum (I & II)

01/19/2014 / No Comments

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 (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
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]

总结:DFS用在这题里,是把每个candidate看成图的点,在数组里相邻的candidate之间就会有一条边,所以在数组排序之后,整个图其实就是一个链表。如果把问题设为F(candidate[],target),假设当前走到的点index是i,那么剩下的问题就是递归调用F(candidate[],target-candidate[i])来找接下来的DFS走法。这里有一点是因为题目规定数可以重复使用,所以每当走完一个结点,并不把他从candidate里拿掉,或者说不把他标记为visited。

然后是Combination SUM II这题,跟之前不一样的是不能重复使用数字(除非一个数字在数组中本来就多次出现),所以我们维护一个visited数组来给用过的数字做标记,还有一个点是要去除duplicate,例如candidate数组里全是1,target也是1,不去重就会得到很多个[1]的解答。

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

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]