题目

39. 组合总和

题解

代码

import java.util.*;

public class code39 {

    public static int sum = 0;

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

    public static void backtrack(List<List<Integer>> res, List<Integer> list, int target, int candidates[], int start) {
        if (sum == target) {
            res.add(new ArrayList<>(list));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (sum + candidates[i] <= target) {
                list.add(candidates[i]);
                sum += candidates[i];
                backtrack(res, list, target, candidates, i);
                sum -= candidates[i];
                list.remove(list.size() - 1);
            }
        }
    }

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

        int[] candidates2 = { 2, 3, 5 };
        int target2 = 8;
        List<List<Integer>> combinationSum2 = combinationSum(candidates2, target2);
        System.out.println(combinationSum2);
    }
}

参考

  1. 学一套走天下(回溯算法)
  2. 回溯算法 + 剪枝（Python 代码、Java 代码）
  3. Leetcode 39：组合总和（最详细的解法！！！）
  4. Leetcode学习笔记-39-组合总和
  5. 39. 组合总和
  6. leetcode 回溯法 模板
  7. 递归，回溯，DFS，BFS的理解和模板
  8. 递归，回溯，DFS，BFS的理解和模板
  9. Java中List的remove方法
  10. Java list.remove( )方法需要注意的两个地方
  11. ArrayList的remove()方法
  12. List 初始化
  13. 全面解析回溯法：算法框架与问题求解