我不喜欢上面看到的Javascript解决方案。下面是我使用部分应用、闭包和递归构建的一个:

好的，我主要关心的是，如果组合数组能满足目标要求，希望这样你就能找到剩下的组合了

这里只需要设置目标并传递组合数组。

function main() {
    const target = 10
    const getPermutationThatSumT = setTarget(target)
    const permutation = getPermutationThatSumT([1, 4, 2, 5, 6, 7])

    console.log( permutation );
}

我提出的当前实现

function setTarget(target) {
    let partial = [];

    return function permute(input) {
        let i, removed;
        for (i = 0; i < input.length; i++) {
            removed = input.splice(i, 1)[0];
            partial.push(removed);

            const sum = partial.reduce((a, b) => a + b)
            if (sum === target) return partial.slice()
            if (sum < target) permute(input)

            input.splice(i, 0, removed);
            partial.pop();
        }
        return null
    };
}

这也可以用来打印所有的答案

public void recur(int[] a, int n, int sum, int[] ans, int ind) {
    if (n < 0 && sum != 0)
        return;
    if (n < 0 && sum == 0) {
        print(ans, ind);
        return;
    }
    if (sum >= a[n]) {
        ans[ind] = a[n];
        recur(a, n - 1, sum - a[n], ans, ind + 1);
    }
    recur(a, n - 1, sum, ans, ind);
}

public void print(int[] a, int n) {
    for (int i = 0; i < n; i++)
        System.out.print(a[i] + " ");
    System.out.println();
}

时间复杂度是指数级的。2^n的阶

Java解决方案的Swift 3转换(by @JeremyThompson)

protocol _IntType { }
extension Int: _IntType {}


extension Array where Element: _IntType {

    func subsets(to: Int) -> [[Element]]? {

        func sum_up_recursive(_ numbers: [Element], _ target: Int, _ partial: [Element], _ solution: inout [[Element]]) {

            var sum: Int = 0
            for x in partial {
                sum += x as! Int
            }

            if sum == target {
                solution.append(partial)
            }

            guard sum < target else {
                return
            }

            for i in stride(from: 0, to: numbers.count, by: 1) {

                var remaining = [Element]()

                for j in stride(from: i + 1, to: numbers.count, by: 1) {
                    remaining.append(numbers[j])
                }

                var partial_rec = [Element](partial)
                partial_rec.append(numbers[i])

                sum_up_recursive(remaining, target, partial_rec, &solution)
            }
        }

        var solutions = [[Element]]()
        sum_up_recursive(self, to, [Element](), &solutions)

        return solutions.count > 0 ? solutions : nil
    }

}

用法:

let numbers = [3, 9, 8, 4, 5, 7, 10]

if let solution = numbers.subsets(to: 15) {
    print(solution) // output: [[3, 8, 4], [3, 5, 7], [8, 7], [5, 10]]
} else {
    print("not possible")
}

c++版本的相同算法

#include <iostream>
#include <list>
void subset_sum_recursive(std::list<int> numbers, int target, std::list<int> partial)
{
        int s = 0;
        for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
        {
            s += *cit;
        }
        if(s == target)
        {
                std::cout << "sum([";

                for (std::list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
                {
                    std::cout << *cit << ",";
                }
                std::cout << "])=" << target << std::endl;
        }
        if(s >= target)
            return;
        int n;
        for (std::list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++)
        {
            n = *ai;
            std::list<int> remaining;
            for(std::list<int>::const_iterator aj = ai; aj != numbers.end(); aj++)
            {
                if(aj == ai)continue;
                remaining.push_back(*aj);
            }
            std::list<int> partial_rec=partial;
            partial_rec.push_back(n);
            subset_sum_recursive(remaining,target,partial_rec);

        }
}

void subset_sum(std::list<int> numbers,int target)
{
    subset_sum_recursive(numbers,target,std::list<int>());
}
int main()
{
    std::list<int> a;
    a.push_back (3); a.push_back (9); a.push_back (8);
    a.push_back (4);
    a.push_back (5);
    a.push_back (7);
    a.push_back (10);
    int n = 15;
    //std::cin >> n;
    subset_sum(a, n);
    return 0;
}

@KeithBeller的回答略有变化的变量名称和一些评论。

    public static void Main(string[] args)
    {
        List<int> input = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
        int targetSum = 15;
        SumUp(input, targetSum);
    }

    public static void SumUp(List<int> input, int targetSum)
    {
        SumUpRecursive(input, targetSum, new List<int>());
    }

    private static void SumUpRecursive(List<int> remaining, int targetSum, List<int> listToSum)
    {
        // Sum up partial
        int sum = 0;
        foreach (int x in listToSum)
            sum += x;

        //Check sum matched
        if (sum == targetSum)
            Console.WriteLine("sum(" + string.Join(",", listToSum.ToArray()) + ")=" + targetSum);

        //Check sum passed
        if (sum >= targetSum)
            return;

        //Iterate each input character
        for (int i = 0; i < remaining.Count; i++)
        {
            //Build list of remaining items to iterate
            List<int> newRemaining = new List<int>();
            for (int j = i + 1; j < remaining.Count; j++)
                newRemaining.Add(remaining[j]);

            //Update partial list
            List<int> newListToSum = new List<int>(listToSum);
            int currentItem = remaining[i];
            newListToSum.Add(currentItem);
            SumUpRecursive(newRemaining, targetSum, newListToSum);
        }
    }'

Thank you.. ephemient

我已经将上述逻辑从python转换为php..

<?php
$data = array(array(2,3,5,10,15),array(4,6,23,15,12),array(23,34,12,1,5));
$maxsum = 25;

print_r(bestsum($data,$maxsum));  //function call

function bestsum($data,$maxsum)
{
$res = array_fill(0, $maxsum + 1, '0');
$res[0] = array();              //base case
foreach($data as $group)
{
 $new_res = $res;               //copy res

  foreach($group as $ele)
  {
    for($i=0;$i<($maxsum-$ele+1);$i++)
    {   
        if($res[$i] != 0)
        {
            $ele_index = $i+$ele;
            $new_res[$ele_index] = $res[$i];
            $new_res[$ele_index][] = $ele;
        }
    }
  }

  $res = $new_res;
}

 for($i=$maxsum;$i>0;$i--)
  {
    if($res[$i]!=0)
    {
        return $res[$i];
        break;
    }
  }
return array();
}
?>