估计面试没通过，唉

[gdw1986]

面试前猎头提示我会考递归，妈的，现学真的搞不定啊，题目是 li = [2,3,5,7,9]，输出任意组合，可以重复选，输出所有和是 13 的组合，递归现学现用失败，还是老老实实拿循环写的：
li = [2,3,5,7,9]

def sum13(li):
for i in li:
if i == 13:
print(i)
for j in li:
if i + j == 13:
print(i,j)
for k in li:
if i + j + k== 13:
print(i,j,k)
for l in li:
if i + j + k + l== 13:
print(i,j,k,l)
for o in li:
if i + j + k + l + o == 13:
print(i,j,k,l,o)

我这是面不过了吧？

[coderluan]

楼主你被误导了, 这题并不是单纯的递归, 单纯的递归一般现学是能搞定的, 这个实际是动态规划问题, 一般解决动态规划问题会用到递归, 但是绝对不是你会递归就能解决动态规划问题.

然后, 我是面试官肯定不给你过了, 不是你不会动态规划和递归, 而是你连循环都不会写, 按你写的, 5 个数你写 5 个变量判断 5 次 15 行代码, 万一工作中要处理 1 万个数, 不得累死你......

[gdw1986]

@coderluan 是的，我觉得也是，哈哈，但是短时间内我实在想不出啥好办法，就硬着头皮写了，总比交白卷强吧

[kop1989]

这……lz 你没有 get 到这个题目的关键点。
这个题目的关键不是真的让你筛选出 5 个数中相加得 13 的。

我帮你翻译翻译：怎么能从 x 个数中“最快”的找到相加为 y 的组合？

[kkbblzq]

问题是你这循环写的也不怎么样啊，5 重循环亏你写得出来，而且也不对，比如有一个数字是 1，按这题的意思可以选 13 次 1

[hikarikun1991]

这是动态规划吧

[gdw1986]

@kop1989 但是还有重复的情况，脑壳疼，我只是面个测试要不要要求这么高

[gdw1986]

@kkbblzq 好吧，你是对的

[gdw1986]

@hikarikun1991 头一次听说这词

[oahebky]

这不是 two sum 吗？

（知道 two sum 的朋友，我有没有理解错题意？）

如果中大厂考我 two sum 我会偷笑...


如果大几十人、100 人刚出头的公司考 two sum 就比较无感，最多觉得公司“身体素质”不错。

[gdw1986]

@oahebky 还可能 one sum 或者 three sum

[wangyzj]

@gdw1986 #6 哈哈哈，面试前刷刷题找找感觉，这玩意一段时间不搞就生疏
不管你搞啥的，先来个算法恶心一下你

[wxsm]

DP 头一次听说？哥们你有点水。

[vipppppp]

感觉可以多看看生成器，最近工作需要，发现这个东西在动态生成数据很有用。

ii = [2, 3, 5, 7, 9, 1]
target = 13


def solution(score=0):
for i in ii:
if score + i == target:
yield [i]
elif score + i < target:
for rs in solution(score + i):
yield [i] + rs


for s in solution():
print(s)

[yhxx]

@oahebky 这是 N sum 吧
比 two sum 还是高了一阶的

[MoYi123]

随便写了一个答案,应该是正解

def solution():
____a = [2, 3, 5, 7, 9]
____ret = []
____memo = set()

____def dp(index, acc):
________if (index, tuple(acc)) in memo:
____________return
________else:
____________memo.add((index, tuple(acc)))
________if index == 5:
____________return
________if sum(acc) == 13:
____________ret.append(tuple(acc))
________if sum(acc) >= 13:
____________return
________dp(index + 1, acc[:])
________dp(index, acc[:] + [a[index]])

____dp(0, [])
____return ret

[oahebky]

哦...

就是有某一个值可以重复取一直加到 13 就可以...

还还是很难的，一时半会我个人想不出高效的思路。

那应该是面的大厂的样子。

[finab]

li 固定为这个数组嘛？ 需要考虑 li 不是 5 个数的情况吧？

递归也可以的，不过性能会比较慢，你这样想


可以先假定有一个函数 叫 comb，可以将数组的数进行组合， 例如输入 [2,3] 就会返回 [[2],[3],[2,3]]
问题就变成了 数组中第一个元素与 comb(数组中其他的元素) 组合

func comb( nums:[Int] ) -> [[Int]] {
if nums.count <= 1 {
//数组中就一个元素，直接原样返回
}
//数组中第一个元素，与 comb(剩下的元素) 返回值 组合起来
for( item in comb(去掉第一个，剩下的元素) ) {
item.insert(nums[0], item.startIndex)
}

//计算最终组合的值，是否等于 13，存在递归之外地方

}

[finab]

@finab 刚写完发现能重复选，那上面的写法是错的 囧~

[georgetso]

@oahebky 这不是 two sum, [可以重复选]

[gdw1986]

@wxsm 哥们只是个测试，确实很水

[devfeng]

什么公司，测试要会动归

[gdw1986]

@devfeng 哈哈哈，一个做大数据的美企

[hello2060]

不是 dp 啦，我不知道这叫什么，模式是很常见的

```
void getall(int[] ar, int cur, List<Integer> current, List<List<Inetger>> rslt, int target) {
if (cur == ar.length) return;

if (sum(current) == target) {
rslt.add(current);
}

for (int i = cur; i < ar.length; i++) {
current.add(ar[i]);
getall(ar, i + 1, current, rslt, target); // 如果每个数只能用一次，不然就从 i 开始
current.remove(curreent.size() - 1);
}
}
```

[jmc891205]

组合的意思就是 5 个数里选 n 个，每个数只能用一次吧

[oahebky]

@georgetso
@yhxx
@gdw1986

👌 确实不是 two sum 。
这种 “不一定多少个 [加数] ” & “数组内的某一个数可以重复选” 的题目我个人还没刷到过，换我我也不会做，哈哈哈哈...

可能暴力解想想会想出来；


leetcode 只刷了一百多 medium，算法菜鸟一个；
最近找到工作入职了就暂停练算法了，所以知道自己菜，一看到算法题就问问有没有理解错题意！

[cnoder]

感觉是 dfs 求所有解 剪剪枝

[gdw1986]

@cnoder 停停，现在内卷这么严重了吗，测试都要会算法了

[boring3b]

是所有 不是最优 就该暴力来吧

[lambdafate]

leetcode 39. 组合总和问题。
可使用 dfs

```
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ret = []
candidates.sort()
self.dfs(candidates, 0, target, [], ret)
return ret

def dfs(self, candidates, index, target, path, ret):
if target == 0:
ret.append(path)
return None
for i in range(index, len(candidates)):
if candidates[i] > target:
break
self.dfs(candidates, i, target-candidates[i], path+[candidates[i]], ret)
```

[lambdafate]

@lambdafate 好家伙，直接乱格式

[8Cangtou]

回溯+剪枝

[ArthurUp]

回溯加剪枝吧

[finab]

还是用递归，时间复杂度十分感人

var result: [[Int]] = []

func comb(nums:[Int], len:Int) -> [[Int]] {
if len == 0 {
return []
}
if len == 1 {
return nums.map { [$0] }
}

var arr:[[Int]] = []
for num in nums {
for var item in comb(nums: nums, len: len - 1) {
item.append(num)
arr.append(item)
}
}
arr.forEach { (item) in
if item.reduce(0, +) == 13 {
result.append(item)
}
}
return arr
}

var nums = [2,3,5]
comb(nums: nums, len: nums.count)
print(result)

[easonHHH]

动态规划吧，定义类似一个二维数组。
先把数组排序，然后>13 的全部舍弃，方便早日跳出循环
假设数组长度为 1 [2]，那可以组合的小于 13 结果就是：[ 2:[[2]]，4:[[2,2]]，6:[[2,2,2]]，8:[[2,2,2,2]]，10:[[2,2,2,2,2]]，12:[[2,2,2,2,2,2]] ]，到 14>13 结束循环
假设数组长度为 1 [2,3]，把 2 的组合+3*N 递归出来，>13 就跳过，直到 3*N>13，结果就是：[ 2:[[2]]，[3],4:[[2,2]]，5:[[2,3]]，6:[[2,2,2],[3,3]]，7:[[2,2,3]]，8:[[2,2,2,2],[2,3,3]]，9:[[3,3,3]]，10:[[2,2,2,2,2],[2,2,3,3]]，11:[[2,2,2,2,3]]，12:[[2,2,2,2,2,2],[2,2,2,3,3],[3,3,3,3]]，13:[[2,2,2,2,2,3],[[2,2,3,3,3]] ]
手写的可能会有纰漏，然后继续，最后把二维数组[13]拉出来就行，而且好像有优化空间，你把[2,4,6,8,10,12].map(n=>{(13-n)%3==0})然后如果余数为 0 就有解的方面入手优化一下
大概思路是这样

[yaphets666]

你是测试啊? 我以为你开发呢 测试怎么考算法...

[nightcatsama]

看到输出所有组合，第一时间想到的是递归加回溯。
```js
function NSum(arr, target) {
let res = []
function dfs(start, list, total) {
if (total >= target) {
if (total === target) res.push([...list])
return
}
for (let i = start; i < arr.length; i++) {
list.push(arr[i])
dfs(i, list, total + arr[i])
list.pop()
}
}
dfs(0, [], 0)
return res
}

NSum([2,3,5,7,9], 13)
```

[9LCRwvU14033RHJo]

@lambdafate 确实是这道题 Combination Sum，还有 Coin Change 2 其实也是类似的吧？

leetcode.com/problems/combination-sum/

leetcode.com/problems/coin-change-2/

[zjlletian]

```
package main

import (
"fmt"
)

var items = []int{2, 3, 5, 7, 9}
var target int = 13

func main() {
findSum([]int{}, 0)
}

func findSum(list []int, sum int) {
for _, i := range items {
if sum+i > target {
return
}
newList := append(list, i)
if sum+i == target {
fmt.Println(newList)
return
}
findSum(newList, sum+i)
}
return
}
```

go 的实现

[gdw1986]

@yaphets666 说实话，听到这题，开始没觉得怎么样，越想越不对，这 TM 就是算法题吧

[Kvip]

不知道能否用第三方库完成，特意去找了下答案

```
from itertools import combinations_with_replacement
li = [2, 3, 5, 7, 9]
for item in combinations_with_replacement(li, 3):
if sum(item) == 13:
print(item)
```
输出结果：
(2, 2, 9)
(3, 3, 7)
(3, 5, 5)

[kera0a]

@Kvip 取的数个数不固定，
还需再套一层循环，个数 3 改成 1 到 n 每个都算一次

[kera0a]

@Kvip 并且 n 并不是 nums.count，仔细想想还挺难的

[9LCRwvU14033RHJo]

@gdw1986
leetcode 题目还有一个限定条件：保证组合不超过 150 种。
所以只要递归法就够了吧。

[MinQ]

num = [2,3,5,7,9]
result = []

def calc(result):
for i in range(0,5):
result.append(num[i])
if sum(result) == 13:
print(result)
result.pop()
return
elif sum(result) < 13:
calc(result)
result.pop()
return

calc(result)

python 的，这样会有重复选择的情况，比如
[2, 2, 2, 2, 2, 3]
[2, 2, 2, 2, 3, 2]
不行的话把结果存下来，再配合个剪枝，应该就行了

[MinQ]

格式丢了，这就尴尬了

[MinQ]

num = [2,3,5,7,9]
result = []


def calc(result):
____for i in range(0,5):
________result.append(num[i])
________if sum(result) == 13:
____________print(result)
____________result.pop()
____________return
________elif sum(result) < 13:
____________calc(result)
________result.pop()
____return


calc(result)

[gdw1986]

@MinQ 感觉你这个靠谱，因为猎头提示了递归，但是我没搞出你这个的结果，格式不对

[MinQ]

@gdw1986 格式的问题，下面那一版已经修正了

[gdw1986]

@MinQ 试了，厉害，应该就是这个答案

[lambdafate]

@user8341 是的，都是一类题

[bwt]

Leetcode 零钱兑换 和这个类似

[smallpython]

不知道递归的意义是什么, 用循环又容易理解, 效率也更高

[aneureka]

这个是完全背包问题🤣

[9LCRwvU14033RHJo]

@lambdafate

题目条件完全一样，只是要求的计算结果不同：一题要求列出所有组合，一题要求计算组合总数。

列出所有组合的这题是不是没办法用动态规划呀？

[eii]

@cnoder 就是这样
```
public class NSum {
static int res = 13;
static int idx = 0;
public static void main(String[] args) {
int[] arr = {2, 3, 5, 7, 9};
Stack<Integer> resStack = new Stack();
traceback(arr, 0, 0,resStack);
}

public static void traceback(int[] arr, int s,int sum,Stack<Integer> resStack){
for (int i = s; i < arr.length; i++) {
int cs = sum + arr[i];
if(cs > res){
break;
}
resStack.push(arr[i]);
if(cs == res){
System.out.println(idx++ + " - " + resStack + " - " + i + " - " + cs);
resStack.pop();
break;
}
traceback(arr,i,cs,resStack);
resStack.pop();
}
}
}
```
```
0 - [2, 2, 2, 2, 2, 3] - 1 - 13
1 - [2, 2, 2, 2, 5] - 2 - 13
2 - [2, 2, 2, 7] - 3 - 13
3 - [2, 2, 3, 3, 3] - 1 - 13
4 - [2, 2, 9] - 4 - 13
5 - [2, 3, 3, 5] - 2 - 13
6 - [3, 3, 7] - 3 - 13
7 - [3, 5, 5] - 2 - 13

[wulin]

背包吧，刷动态规划

[gdw1986]

@wulin #56 背包是什么意思？

[lu5je0]

public static List<List<Integer>> cal(int[] arr, int target) {
List<List<Integer>> results = new ArrayList<>();
func(results, new ArrayList<>(), arr, target, 0);
return results;
}

public static void func(List<List<Integer>> results, List<Integer> curList, int[] arr, int target, int start) {
int num = curList.stream().mapToInt(value -> value).sum();
if (num > target) {
return;
}

if (num == target) {
results.add(new ArrayList<>(curList));
} else {
for (int i = start; i < arr.length; i++) {
curList.add(arr[i]);
func(results, curList, arr, target, i);
curList.remove(curList.size() - 1);
}
}
}
回溯法吧

[Taikyo]

滑动窗口算法应该可以解这道题吧

[binux]

这题有更好的解法，但是暴力的解法你也没做对啊。

[Mrun]

老铁，这个是 leetcode 的原题

可以参考一下这个答案

https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/

[Mrun]

@oahebky #25 leetcode 39 和 40，这个是面试的经典题型

[kuangwinnie]

@oahebky 不是 2sums

[ericgui]

这是 dfs

你要刷 dfs

[xrr2016]

第一眼看上去要用回溯法

[SuperXRay]

dfs + 剪枝 也是递归的一种嘛，猎头没骗你
找测试的话，如果非写代码自动化测试的那种，面这个真的过分了
就说技术岗，我觉得现场写不出来的也有很多

如果并不要求写出正确答案，只从你的解答来看观察专业水平的话，倒也合理

[dany813]

面试前还是先刷下算法吧

[simonlu9]

感觉和爬楼梯有多少种爬法一个解法

[meathill]

楼主让我想起了最近被我开掉的那个哥们儿。说的话听起来好像都懂，表现不好可能是因为临场没发挥出来。结果往细里一看差的不是一点半点。

[ymyqwe]

dfs 啊，套路都差不多的，怎么剪枝优化才是重点

[salamanderMH]

回溯法可以做这道题。

[fcoolish]

这两天刚做了这题，回溯 + 剪枝，题目类型还分数字能不能重复使用。

[18870715400]

这个应该是回溯吧
def f(lst, target):
ans = []
def dfs(val_index, index):
if sum([lst[i] for i in val_index]) == target:
ans.append([lst[i] for i in val_index])
return
if sum([lst[i] for i in val_index]) > target:
return
for i in range(index, len(lst)):
if i in val_index:
continue
dfs(val_index+[i], i+1)
dfs([], 0)
return ans

print(f([1, 2, 3, 4, 5, 6, 7], 8))

[jtwor]

回溯把。。

[tianhualefei]

这是 leetcode 上面第 518 题，的零钱兑换问题 II，给定不同面额的硬币个一个总金额，写出函数计算可以凑成总金额额额硬币组合数。假设每种面额的硬币无限个。

状态表示 dp[i][j]，表示数组前 i 个数[0.....i-1]组成金额为 j 的硬币组合数。
第 i 种货币可以不拿，可以拿 1…n 次。
递推方程 dp[i][j]=dp[i-1][j]+dp[i-1][j-coni[i]]+dp[i-1][j-k*coin[i]]，简化为
dp[i][j]=dp[i-1][j]+dp[i][j-coin[i]]或一维的 dp[j]=dp[j]+dp[j-coin[i]]。

[b1ackjack]

dfs 可解，leetcode 有原题

[allforone]

楼上正解

[caoyouming]

func combinationSum(candidates []int, target int) [][]int {
return findSum(candidates, target)
}

func findSum(candidates []int, target int) [][]int {
var result [][]int
var list []int
var sum int
for _,val :=range candidates{
if sum + val > target{
return result
}else{
newList := append(list,val)
if sum + val == target{
result = append(result, newList)
}else{
findSum(newList, sum + val)
}
}
}
return result
}

[GroupF]

我就留个眼睛吧

[tankren]

还需努力 加油吧 虽然我不会写代码。。

[cyrbuzz]

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%
的用户

[xuxuzhaozhao]

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

[balaWgc]

竟然是面试测试，啥厂啊

[ppcoin]

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

[blackshow]

如果是白板题,可能很大概率写不出来.
```
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;
}
}

```

[kanemochi]

递归+减枝可以解决

[maplelin]

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

[maplelin]

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

[9LCRwvU14033RHJo]

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

[xe2vherd]

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

[aijam]

https://gist.github.com/czheo/4046ec98c513109375f65cd9c677bbcd

[GoLand]

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

[no1xsyzy]

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

[gmywq0392]

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

[no1xsyzy]

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

@easonHHH @cyrbuzz 这是 BFS 吧（

[fsworld]

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)

[easonHHH]

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

[Hieast]

这是面的啥级别，P6 ？

[gaigechunfeng]

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

[no1xsyzy]

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