关于整型数组排列组合的问题

Question

int[] a = {1,2,3,4,5,6};
int b = 10;

for (int i=0;i<1<<a.length;i++){
int sum = 0;
String s = "";
for (int j=0;j<a.length;j++){
if ((i>>j&1)==1){
sum += a[j];
s += a[j]+" ";
}
}
if (sum==b){
System.out.println(s);
}
}

Answer 1

这个用普通的递归结合回溯来解决吧。给出一个python的算法，可以支持int数组内有负数的情形。如果能够保证数组中只有非负数的话，下面这个算法还可以稍作修改，结合剪枝策略来达到更小的时间消耗。
class Solution:    def __init__(self):
        self.nums = None
        self.len_nums = 0
        self.total = 0
        self.combinations = [ ]    def doGetlCombination(self, prefix, prefix_total, start):
        if start >= self.len_nums:
            return
        num = self.nums[start]
        if prefix_total + num == self.total:
            new_prefix = prefix[:]
            new_prefix.append(num)
            self.combinations.append(new_prefix)
        if prefix_total + num <= self.total:
            new_prefix = prefix[:]
            new_prefix.append(num)
            self.doGetlCombination(new_prefix, prefix_total + num, start + 1)
        self.doGetlCombination(prefix, prefix_total, start + 1)    def getAllCombination(self, nums, total):
        self.nums = nums
        self.len_nums = len(self.nums)
        if 0 == self.len_nums:
            return [ ]
        self.total = total
        self.doGetlCombination([ ], 0, 0)
        return self.combinationsdef main():
    nums = [1, 2, 3, 4, 5, 6, -1, 1]
    total = 10
    solu = Solution()
    print solu.getAllCombination(nums, total)

Answer 2

这是一个典型的背包问题，其复杂度是O（2^n). 11楼说是O^2是不是打错了。基本思路是求n个元素的所有组合，n个元素的所有组合=c(n,0) + c(n,1) + ... c(n,n)=2^n. 不过在枚举过程中可采用适当的顺序和策略，提前过滤掉不可能的分支以加快搜索速度。