估计面试没通过，唉

dp 走一波。

```
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
// 思路就是 dp
// 比如 target 2 的解是子问题 1 的解+子问题 1 的解，和 2 自己
// target 3 的解可以是子问题 1 的解+子问题 1 的解+子问题 1 的解 / 子问题 1 的解+子问题 2 的解和 3 自己
// target 4 的解就是 3 的解+1+自己。
// 变一下这个思路，7 的解应该是自己(如果有) + 6 - 1 中的组合。
// 还可继续优化。

candidates = candidates.sort((a, b) => {
return a - b
})

let _find = {}

candidates.map((item) => {
_find[item] = 1
})

let dp = [
]

if (candidates[0] === 1) {
dp.push({
num: 1,
sub: [[1]]
})
} else {
dp.push({
num: 1,
sub: []
})
}

for (let i=2; i <= target; i++) {
let sub = []
let old = {}
for (let j = i-1; j > 0; j--) {
if (dp[j-1].sub.lenght !== 0 && _find[i-j]) {
for (let c of dp[j-1].sub) {
let temp = [...c, i-j].sort((a, b) => {
return a - b
})
if (!old[temp.join('')]) {
sub.push(temp)
old[temp.join('')] = 1
continue
}

}
}
}

if (_find[i]) {
sub.push([i])
}

dp.push({
num: i,
sub: sub
})
}

// console.log(dp[dp.length - 1].sub)
return dp[dp.length - 1].sub
};
```

https://leetcode-cn.com/problems/combination-sum/

执行用时：
156 ms
, 在所有 JavaScript 提交中击败了
11.81%
的用户
内存消耗：
46.9 MB
, 在所有 JavaScript 提交中击败了
5.04%
的用户

这也太严格了，测试都要考算法了吗

竟然是面试测试，啥厂啊

动态规划不能做让你列出所有结果的问题

如果是白板题,可能很大概率写不出来.
```
public class SumTest {

public static void main(String[] args) {
Integer[] li = new Integer[]{2, 3, 5, 7, 9};
int target = 13;
List<Integer[]> sum = sum(li, target);
for (Integer[] i : sum) {
System.out.print(Arrays.toString(i));
}
}

private static List<Integer[]> sum(Integer[] args, int target) {
List<Integer> nums = Arrays.asList(args);
List<Integer[]> result = new ArrayList<>();
for (int i = 0; i < (args.length % 2 == 0 ? args.length / 2 : args.length / 2 + 1); i++) {
int num = args[i];
int sum = num;
int count = 1;
while (target - sum > 0) {
List<Integer> temp = new ArrayList<>();
for (int j = 0; j < count; j++) {
temp.add(num);
}
if (nums.contains(target - sum)) {
temp.add(target - sum);
result.add(temp.toArray(new Integer[0]));
}
sum = sum + args[i];
count++;
}
}
return result;
}
}

```

递归+减枝可以解决

回溯算法，经典的可以重复取值和不能重复取值，算法的核心在于怎么剪枝掉暴力枚举会出现的重复计算，或者多余计算。如果从最小的值开始依次取，一旦和大于 13 之后在枚举就没有意义了，就需要剪枝。

楼主这是直接用的暴力法，估计是不合格了，因为核心考点就是剪枝，不剪枝基本在刷题网站都是直接判超时不给通过的

暴力解也得写对呀。不是胡乱瞎写就叫做暴力解。

看看 sicp 看完后只会递归了，循环是什么？

这其实就是遍历二叉树，广度遍历，每个节点的子节点都是数组里的所有数，和大于 13 的节点就剪枝。最后生成的树就是你要的答案。其实还是暴力递归。

@zmxnv123 你这显然只看了一半，sicp 不是明确指出递归可以方便地转写成迭代了吗？

回溯标准题, 具体表现是递归+剪枝.

不确定选取个数啊，那确实是剪枝完事

@easonHHH @cyrbuzz 这是 BFS 吧（

JavaScript 版本的：

var li = [2, 3, 5, 7, 9]

function getCombination(target, arr = []) {
li.forEach(value => {
if (target - value < 0) {
return
}
if (target - value === 0) {
console.log(arr.concat(value))
return
}
getCombination(target - value, arr.concat(value))
})
}

getCombination(13)

@no1xsyzy #95
这属于动态规划的完全背包问题也不矛盾吧，算法题多种思路解也很常见

这是面的啥级别，P6 ？

还是继续努力吧。没办法，既然要吃这碗饭，出去面试都考这个。别人学，你也得学。

@easonHHH 我是说你们俩写出来的都是 BFS……