组合和调试

Question

我已经编写了一些代码来尝试解决这个挑战，但它不起作用，我似乎无法弄清楚哪里出了问题，我可以在网上找到答案，但这不是我尝试的重点看看为什么我的代码不起作用。

问题：

给定一组候选数字 (candidates)（无重复）和一个目标数字 (target)，找出候选数字总和为 target 的所有唯一组合。

可以无限次地从候选人中选择相同的重复数字。

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

这是我想出的：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res,new ArrayList<Integer>(), candidates,target,0,0);
        return res;
    }
    //current = current sum, we want it to be target
    //start is index we are at and where the for loop starts

    public void helper(List<List<Integer>> res, List<Integer> temp, int[] nums, int target, int current, int start){
        if(start>=nums.length){
            return;
        }
        if(current>=target){
            if(current==target){
                res.add(new ArrayList<>(temp));
            }
            temp.remove(temp.size()-1);
            helper(res,temp,nums,target,current-nums[start],start+1);
            return;
        }
        for(int i=start; i<nums.length; i++){
            temp.add(nums[i]);
            helper(res,temp,nums,target,current+nums[i],start);
        }
    }
    
}

我的代码说明：

所以我想在这里使用递归回溯。我一直循环数组中的一个元素，直到总和 >= target.if 它的 >target 我删除了最后一个元素，因为它比 target 大并尝试其他元素。如果 its = target 我将它添加到结果中，然后删除最后一个元素以尝试找到更多组合。

但显然我在这一行中遇到了错误：

temp.remove(temp.size()-1); //saying index out of bounds i am trying to remove when arraylist is empty

所以这不是运行我的想法，因为如果列表为空，当前应该为 0，它甚至应该进入 if 循环并且永远不应该被删除，但它确实是，我不确定为什么。

谢谢。

Answer 1

试试这个。

static List<List<Integer>> combinationSum(int[] candidates, int target) {
    int size = candidates.length;
    List<List<Integer>> result = new ArrayList<>();
    new Object() {
        void search(int index, int sum, List<Integer> selected) {
            if (index >= size) {
                if (sum == target)
                    result.add(new ArrayList<>(selected));
            } else {
                int candidate = candidates[index];
                List<Integer> nextSelected = new ArrayList<>(selected);
                for (int nextSum = sum; nextSum <= target; nextSum += candidate, nextSelected.add(candidate))
                    search(index + 1, nextSum, nextSelected);
            }
        }
    }.search(0, 0, new ArrayList<>());
    return result;
}

和

int[] candidates = {2, 3, 6, 7};
int target = 7;
List<List<Integer>> result = combinationSum(candidates, target);
System.out.println(result);

结果：

[[7], [2, 2, 3]]

Answer 2

主要问题 if 尝试回滚当前变量值并在 if(current>=target) if 语句中再次调用辅助方法。您可以使用 for 循环自动为您执行此操作，并删除 returns 之后添加的数字。然后使用函数 return 更新起始值，以便它从您停止的地方继续，从而消除重复项。

而且由于 for 循环 num[i] 永远不会越界所以你不必担心

if(start>=nums.length){
            return;
        }

这是使用您的解决方法的工作版本

public static List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> res = new ArrayList<>();
    helper(res,new ArrayList<Integer>(), candidates,target,0,0);
    return res;
}

public static int helper(List<List<Integer>> res, List<Integer> temp, int[] nums, int target, int current, int start){

    if(current>=target){
            
        if(current==target){
            res.add(new ArrayList<>(temp));
        }
        return start + 1;
    }
    for(int i=start; i<nums.length; i++){
        temp.add(nums[i]);
        start = helper(res,temp,nums,target,current+nums[i],start);
        temp.remove(temp.size()-1);
    }
    return start;
}

运行代码：

public static void main(String []args){
        List<List<Integer>> res = combinationSum(new int[] {2,3,6,7}, 7);
        System.out.println(res);
}

结果：

[[2, 2, 3], [7]]

组合和调试

Combination Sum Debugging

java

arrays

recursion

backtracking