Java

Question

我运行在获取名为 res 的 List<List<Integer>> 的价值时遇到了问题。这是一个递归调用，该调用应该填充此“res”，但是当另一个函数调用递归函数并且该函数返回一个空列表时。但是当我记录它时，我可以看到这些值。这是代码：

class Solution {
    public List<List<Integer>> combinationSum(int[] arr, int k) {
        // given an arr and a sum k, find all the subsequences that sum upto k
            // we can use backtracking here as we need all the options
            // there are 2 choices for every element:
            // either we can take it in the subres or discard it
            // if we take it once, we can take it n times till the target is reached
            
            Arrays.sort(arr);
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> subRes = new ArrayList<>();

            combinationSum(0, arr, k, 0, res, subRes);

            return res;
    }
  
    public void combinationSum(int i, int[] arr, int k, int sum,
                                              List<List<Integer>> res, 
                                              List<Integer> subRes){
          if(sum == k) {
            if(!res.contains(subRes)) res.add(subRes);
            System.out.println("res = " + res);
            return;
          }

          if(i == arr.length || sum > k) return;

          subRes.add(arr[i]);
          sum += arr[i];
      
          combinationSum(i, arr, k, sum, res, subRes);

          subRes.remove(new Integer(arr[i]));
          sum -= arr[i];

          combinationSum(i + 1, arr, k, sum, res, subRes);
      
        }
}

我对此深陷其中，提前致谢。

Answer 1

您在递归中对 subRes 所做的更改会影响您在 res 中看到的内容。在将 subRes 添加到 res 之前，制作一个 新副本 。

 if(!res.contains(subRes)) {
     res.add(new ArrayList<>(subRes));
}

在您的代码中，正确的列表 (subRes) 被添加到 res，但是您 mutate/modify subRes 稍后在递归调用 returns.

Java - 值在递归调用后未反映

Java - Values aren't reflecting after recursion call

recursion

backtracking