数组面试题-子集和问题

题目描述

给定一个含有n个元素的整形数组，再给定一个和sum，求出数组中满足给定和的所有元素组合存在一个数组中。

解法之一：回溯法

分析：对于数组中任意一个元素，先将其放入结果集中，如果当前和不超出给定和，那就继续考察下一个元素，如果超出给定和，则舍弃当前元素。如此往复，直到找到所有可行解。

//给定一个含有n个元素的整形数组，再给定一个和sum，求出数组中满足给定和的所有元素组合

/**
 * arr : 目标数组
 * sum : 给定的和
 * res : 结果数组
 * c : 符合条件的数组子集
 * n : 数组长度
 * t : 当前子集存储的元素个数
 */
var arr = [5, 2, 3, 4, 11, 6, 7, 8, 9];
var res = [];
var c = [];
var sum = 10;

function fixedSum(arr, n, t, sum) {
    if (sum === 0) {
        res.push(c.slice(0));
    } else {
        if (t === n) {
            return;
        } else {
            c.push(arr[t]);
            if (sum - arr[t] >= 0) {
                fixedSum(arr, n, t + 1, sum - arr[t]);
            }
            c.pop();
            if (sum >= 0) {
                fixedSum(arr, n, t + 1, sum);
            }
        }
    }
}

fixedSum(arr, arr.length, 0, sum);
console.log(res);

示例代码输出结果为：[ [ 5, 2, 3 ], [ 2, 8 ], [ 3, 7 ], [ 4, 6 ] ]

解法参考:
http://www.cnblogs.com/graphics/archive/2011/07/14/2105195.html