开始刷题，之前几乎没用java写过算法题

这道题是一个典型的"组合总和"问题,属于回溯算法的范畴。

问题类型:

这个问题可以归类为"组合问题",也就是求出所有可能的组合方案。与之相对应的还有排列问题。组合问题的特点是:不关心元素的顺序,只关心最终的组合结果。

算法思路:

这个问题的解决使用了回溯算法(Backtracking)。回溯算法是一种通用的算法思想,它通过不断尝试构造候选解,并在确定该候选解不是最终解的时候回溯,尝试别的可能的候选解。

具体到这个问题,回溯算法的实现步骤如下:

1. 从输入数组 candidates 中选择一个数字,加入到当前组合中。
2. 检查当前组合的和是否等于目标值 target。如果是,则将该组合加入到结果集中。
3. 如果当前组合的和小于目标值,则递归地尝试从 candidates 中选择下一个数字,加入到当前组合中。
4. 如果当前组合的和大于目标值,则无需继续尝试,直接回溯。
5. 回溯的时候,将上一步加入的数字从当前组合中移除,尝试其他可能的选择。

算法复杂度:

• 时间复杂度: O(N * 2^N),其中 N 是 candidates 的长度。每个数字都可以选择无限次,因此总共有 2^N 种可能的组合。对于每种组合,我们还需要花费 O(N) 的时间来构造它。
• 空间复杂度: O(N),用于存储最终的结果集。递归调用的深度最大为 N。

总的来说,这是一个典型的回溯算法问题,通过不断尝试构造候选解,并在确定不可行时回溯,最终得到所有可能的组合方案。这种算法思想在许多类似的组合问题中都会用到。

java
class Solution {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 先对 candidates 数组进行排序
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> combination, int[] candidates, int remain, int start) {
        if (remain < 0) {
            return;
        } else if (remain == 0) {
            result.add(new ArrayList<>(combination));
        } else {
            for (int i = start; i < candidates.length; i++) {
                combination.add(candidates[i]);
                backtrack(result, combination, candidates, remain - candidates[i], i);
                combination.remove(combination.size() - 1);
            }
        }
    }

}

接下来是相似题目

java

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), n, k, 1);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> currentCombination, int n, int k, int start) {
        if (currentCombination.size() == k) {
            result.add(new ArrayList<>(currentCombination));
            return;
        }

        for (int i = start; i <= n; i++) {
            currentCombination.add(i);
            backtrack(result, currentCombination, n, k, i + 1);
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}

相似题目2

java
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), k, n, 1);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> currentCombination, int k, int n, int start) {
        if (currentCombination.size() == k) {
            if (getSum(currentCombination) == n) {
                result.add(new ArrayList<>(currentCombination));
            }
            return;
        }

        for (int i = start; i <= 9; i++) {
            currentCombination.add(i);
            backtrack(result, currentCombination, k, n, i + 1);
            currentCombination.remove(currentCombination.size() - 1);
        }
    }

    private int getSum(List<Integer> combination) {
        int sum = 0;
        for (int num : combination) {
            sum += num;
        }
        return sum;
    }
}

相似题目3

java
class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 先对 candidates 数组进行排序
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> combination, int[] candidates, int remain, int start) {
        if (remain < 0) {
            return;
        } else if (remain == 0) {
            result.add(new ArrayList<>(combination));
        } else {
            
            for (int i = start; i < candidates.length; i++) {
                 if (i > start && candidates[i] == candidates[i - 1]) {
                    continue; // 跳过重复的数字
                }
                combination.add(candidates[i]);
                backtrack(result, combination, candidates, remain - candidates[i], i + 1);
                combination.remove(combination.size() - 1);
            }
        }
    }

}

java
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1; // 当目标值为 0 时,存在一种组合方式

        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                }
            }
        }

        return dp[target];
    }
}

相似题目4

java
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> currentPermutation, int[] nums) {
        if (currentPermutation.size() == nums.length) {
            result.add(new ArrayList<>(currentPermutation));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (currentPermutation.contains(nums[i])) {
                    continue;
                }
                currentPermutation.add(nums[i]);
                backtrack(result, currentPermutation, nums);
                currentPermutation.remove(currentPermutation.size() - 1);
            }
        }
    }
}