递归代码在 Javascript 中给出错误答案

Question

我想在 Javascript 中使用回溯打印数组的所有子集我的算法是正确的，但它给出了一些意想不到的答案。我认为这与 javascript 语言有关。

// this is base function where i am calling recursive function .
function solveIt(A,B,C,D,E){
      let ans = [];   // this is ans array
      let sub = [];    // this is subset array 
      printAllSubset(A,0,sub,ans); // Calling the helper function
      return ans;    // returing anser
       
    
}

// My recursive code 
function printAllSubset(nums,idx,sub,ans){
    
    if(idx==nums.length){.   // This is base condition
        ans.push(sub);
       
        return ans;
        
    }
    // include current index
    sub.push(nums[idx]);            // including the current index
    printAllSubset(nums,idx+1,sub,ans);  // recuring for all possible sub problem
    
    // exclude current index
    
    sub.pop();                            // excluding the current index
    printAllSubset(nums,idx+1,sub,ans);   // recuring for all possible scenerio
     
    
}

const A=[1,2,3];
const res = solveIt(A,B,C);

console.log(res)

// output I am getting - 
[
  [], [], [], [],
  [], [], [], []
]

// But the expected output should be - 

[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Answer 1

这里的问题是您将相同的 sub 数组添加到 ans，并且对 sub 的任何更改也会反映在 ans 数据中。因此，您需要添加 sub 的副本：

const A=[1,2,3];
const res = solveIt(A);

console.log(res)

// this is base function where i am calling recursive function .
function solveIt(A,B,C,D,E){
      let ans = [];   // this is ans array
      let sub = [];    // this is subset array 
      printAllSubset(A,0,sub,ans); // Calling the helper function
      return ans;    // returing anser
       
    
}
// My recursive code 
function printAllSubset(nums,idx,sub,ans){
    
    if(idx==nums.length){   // This is base condition
        ans.push([...sub]); // push a copy of the array
       
        return ans;
        
    }
    // include current index
    sub.push(nums[idx]);            // including the current index
    printAllSubset(nums,idx+1,sub,ans);  // recuring for all possible sub problem
    
    // exclude current index
    
    sub.pop();                            // excluding the current index
    printAllSubset(nums,idx+1,sub,ans);   // recuring for all possible scenerio
     
    
}

Answer 2

您努力在 ans 中找到答案，但随后将其丢弃。一个答案是使 ans 成为全局变量并将其从递归函数调用中删除：

let ans=[]
function solveIt(A){ 
      printAllSubset(A,0,[]); // Calling the helper function
}

function printAllSubset(nums,idx,sub){

    if(idx===nums.length){.   // This is base condition
        ans.push(sub);
    }
    // include current index
    sub.push(nums[idx]);            // including the     current index
    printAllSubset(nums,idx+1,sub);  // recuring for all possible sub problem

    // exclude current index

    sub.pop();                            // excluding the current index
    printAllSubset(nums,idx+1,sub);   // recuring for all possible scenerio
}

另一种是捕获递归调用printAllSubset的return:

function solveIt(A){ 
      return printAllSubset(A,0,[],[]); // Calling the helper function
}

function printAllSubset(nums,idx,sub,ans){

    if(idx===nums.length){.   // This is base condition
        ans.push(sub);
   
        return ans;
    
    }
    // include current index
    sub.push(nums[idx]);            // including the     current index
    ans=printAllSubset(nums,idx+1,sub,ans);  // recuring for all possible sub problem

    // exclude current index

    sub.pop();                            // excluding the current index
    ans=printAllSubset(nums,idx+1,sub,ans);   // recuring for all possible scenerio

    return ans;
}

Answer 3

这里的其他答案显示了您的代码有什么问题以及如何修复它。我只想演示一种更清晰的递归方式来编写此代码：

const powerset = ([x, ...xs] = []) =>
  x == undefined
    ? [[]]
    : powerset (xs) .flatMap (ys => [ys, [x, ...ys]])

console .log (JSON .stringify (powerset ([1, 2, 3])))

与所有递归一样，一种有用的思考方式是认识到它适用于基本情况，并且如果每个递归调用都朝着基本情况取得进展，并且我们是否可以看到它何时适用我们的递归调用它也适用于我们当前的调用，那么我们可以确信它适用于所有情况。因为 powerset ([]) //=> [[]]，它适用于基本情况。因为每次递归调用都涉及将我们的输入数组缩小一，所以我们的第二个条件成立；我们最终会达到一个基本案例。我们通过示例展示的第三个条件：我们假设 powerset ([2, 3]) 正确地产生 [[], [2], [3], [2, 3]]，那么 powerset ([1, 2, 3]) 将产生

[[], [2], [3], [2, 3]] .flatMap (ys => [ys, [1, ...ys]])

与

相同

[... [[], [1]], ... [[2], [1, 2]], ... [[3], [1, 3]], ... [[2, 3], [1, 2, 3]]]
//    `--[]--'      `----[2]----'       `----[3]----'     `------[2, 3]------'

简直就是

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

等递归案例正常工作。不难证明所有的子集都会用这种技术出现。我们只是将上面的例子形式化。

但这意味着此函数将准确捕获表示为 JS 数组的集合的幂集。

递归代码在 Javascript 中给出错误答案

Recursive code gives wrong answer in Javascript

javascript

algorithm

recursion

backtracking

data-structures