算法题 求一个数组中任意个元素的组合

[leonidas]

碰到的一个 PHP 面试题

例如有个数组：
$arr = [1,2,3,4,5,6,7,8,9];
求出该数组任意个元素的组合，并不重复
类似
$result = [
[1,2],
[1,3],
[1,4],
[1,5],
[1,2,3],
[2,3,4],
...
...
];





-------------------------------------分割线-------------------------------------

扩展：
给出一个值，如：
$n = 20.2
求出上述数组中，任意个元素的组合相加后与该值最接近的组合

也就是类似说的背包问题



有大佬有解法吗，当时没有想到好的解法

[sean10]

leetcode 排列组合问题 模板
https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)

[ipwx]

题目要求输出所有组合。所以数组长度必然不大，毕竟最后的存储空间要达到 sizeof(int) * n * 2^n 字节。所以我们假设 n < 32。所以可以 for (unsigned int i=0; i<(1<<n); ++i)，然后在循环里面根据 i 的二进制位（是否为 1 ），选择元素，生成列表。

[msg7086]

扩展不是背包问题吧？

[leonidas]

@msg7086 嗯 类似背包问题

[leonidas]

@ipwx
@sean10
额 表示没看懂。。

[msg7086]

把数字转换成二进制，是 1 的位就选出对应的数字下标，是 0 就不选，然后本题应该是要去掉只有一个数的数组吧，过滤一下就好了。