[LeetCode][JavaScript]Combination Sum III

浏览数：231 / 时间：2015年06月08日

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

我做到现在AC最快的题目，真的不到1分钟，还是上两题的变通：

把第二题的代码copy过来，删掉visited，candidates换成一到9，最后加上个数的限制，就好了。

真会玩啊，一个类型翻来覆去，很欢迎Combination Sum IV

 1 /**
 2  * @param {number} k
 3  * @param {number} n
 4  * @return {number[][]}
 5  */
 6 var combinationSum3 = function(k, n) {
 7     var res = [];
 8     var candidates = [1,2,3,4,5,6,7,8,9];
 9     candidates.sort(sorting);
10     bfs(0, -1, []);
11     return res;
12 
13     function bfs(sum, index, tmp){
14         var newTmp = null;
15         if(sum === n && tmp.length === k){
16             newTmp = tmp.concat();
17             res.push(newTmp);
18             return;
19         }else if(tmp.length > k || sum > n || index + 1 >= candidates.length){
20             return; //pruning
21         }
22 
23         for(var i = index + 1; i < candidates.length; i++){
24             newTmp = tmp.concat();
25             newTmp.push(candidates[i]);
26             bfs(sum + candidates[i], i, newTmp);
27         }
28     }
29     function sorting(a, b){
30         if(a > b){
31             return 1;
32         }else if(a < b){
33             return -1;
34         }else{
35             return 0;
36         }
37     }
38 };