javascript - 查找数组中的所有子集，递归不起作用，JavaScript

Question

我正在尝试实现给定一组不同的整数 S，返回所有可能的子集问题。

[A, B, C] 应该给出 [ [ ], [A], [A, B], [A, B, C], [A, C], [B], [B, C], [C] ].

无法弄清楚为什么函数不回溯。

对于输入 [A, A, B, C]，我的实现输出 [ [], ["A"], ["A", "A"], ["A", "A", "B"], ["A", "A", "B", "C"]]

这是我的代码。

var subsets = function(A){
  /*for input [ A, A, B, C ], appendCount returns [ [A, 2], [B, 1], [C,1] ]*/
  var arr = appendCount(A);
  result =[[]];
  var tempArr = [];

  var findSubsets = function(index, tempArr, a) {
    var arrCopy = a.slice();
    while(index < arrCopy.length) {
      if(arrCopy[index][1] > 0) {
        tempArr.push(arrCopy[index][0]);
        result.push(tempArr.slice());
        var newArr = arrCopy.slice();
        newArr[index][1] -= 1;
        findSubsets(index, tempArr, newArr);
        tempArr.pop();
        index++;
   } else {
       index++;
   }
 } 
}
 findSubsets(0, tempArr, arr.slice());
 return result;
}

提前致谢

Answer 1

递归

function findSubsets( array, position ){
    position = position || 0;

    if (position >= array.length) return [[]];

    var output = findSubsets( array, position + 1 );

    for (var i = 1, endI = output.length; i < endI ; i++){
        output.push( 
            output.slice(i, i+1).concat( array[position] )
        );
    };

    return output.concat( array[position] );
};

迭代

function findSubsetsIterative( array ){
    var output = [];

    for (var n = 0 , limit = 1 << array.length ; n < limit ; n++) {
        var subSet = [];
        for (var i = n, p = 0; i ; i >>= 1, p++){
            if (i & 1) subSet.push( array[p] );
        };
        output.push( subSet )
    };

    return output;
};