神马都会亿点点的毛毛张

一万次悲伤，依然会有Dream

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 2k 阅读时长 ≈ 3 分钟
回溯算法练习题 | 子集问题
LeetCode链接：78. 子集

题目1：78. 子集

1.题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

2.题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    // 定义一个列表 result，用于存储最终生成的所有子集
    List<List<Integer>> result = new ArrayList<>();
	// path 用于存储当前路径的子集
    List<Integer> path = new ArrayList<>();
    // 主方法 subsets，输入一个整数数组 nums，返回所有可能的子集
    public List<List<Integer>> subsets(int[] nums) {
        // 调用回溯算法生成所有子集，初始从索引 0 开始
        backtracking(nums, 0);
        // 返回结果列表
        return result;
    }

    // 回溯算法方法 backtracking，构建不同大小的子集
    public void backtracking(int[] nums, int start) {
        // 每次递归调用时，将当前路径 path 的副本加入结果列表中
        result.add(new ArrayList<>(path));

        // 如果 start 已经到达数组末尾，直接返回
        if (start >= nums.length) return;

        // 遍历数组，从 start 开始选择当前元素作为子集的一部分
        for (int i = start; i < nums.length; i++) {
            // 将当前元素加入路径 path
            path.add(nums[i]);
            // 递归调用 backtracking 处理下一个元素，生成包含当前元素的子集
            backtracking(nums, i + 1);
            // 回溯：移除最后加入的元素，尝试其他组合
            path.remove(path.size() - 1);
        }
    }
}

题目2：90. 子集 II

1.题目描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

1
2
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

2.题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 存储最终的子集结果
    List<Integer> path = new ArrayList<>(); // 存储当前路径的子集

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // 排序以便去重
        backtracking(nums, 0); // 从索引 0 开始回溯
        return result; // 返回所有子集结果
    }

    public void backtracking(int[] nums, int start) {
        result.add(new ArrayList<>(path)); // 将当前路径加入结果列表
        if (start == nums.length) return; // 递归结束条件
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // 跳过重复元素
            path.add(nums[i]); // 将当前元素加入路径
            backtracking(nums, i + 1); // 递归处理下一个元素
            path.remove(path.size() - 1); // 回溯：移除最后添加的元素
        }
    }
}

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 2.5k 阅读时长 ≈ 4 分钟

回溯算法练习题

LeetCode链接：131. 分割回文串

题目1：131. 分割回文串

1.题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
输入：s = "a"
输出：[["a"]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

2.题解

2.1 回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    // 保存所有符合条件的回文分割方案
    List<List<String>> result = new ArrayList<>();
    // 当前回溯路径，用于保存一次递归过程中生成的回文子串
    List<String> path = new ArrayList<>();

    // 主函数，接收字符串并启动回溯过程
    public List<List<String>> partition(String s) {
        // 从字符串的第 0 个字符开始进行回溯
        backtracking(s, 0);
        // 返回最终的所有回文分割方案
        return result;
    }

    // 回溯函数，递归生成回文子串的组合
    public void backtracking(String s, int start) {
        // 当 start 达到字符串末尾时，说明已经找到了一个完整的分割方案
        if (start == s.length()) {
            // 将当前路径（回文组合）添加到结果列表中
            result.add(new ArrayList<>(path));
            return;
        }

        // 从 start 开始，尝试截取不同长度的子串
        for (int i = start; i < s.length(); i++) {
            // 获取从 start 到 i 的子串
            String sub = s.substring(start, i + 1);
            // 如果子串是回文，则将其加入路径并继续递归
            if (isPalindrome(sub)) {
                // 添加当前回文子串到路径中
                path.add(sub);
                // 递归处理从 i+1 开始的剩余字符串
                backtracking(s, i + 1);
                // 回溯，撤销上一步的选择，将最后一个子串移除
                path.remove(path.size() - 1);
            }
        }
    }

    // 判断字符串是否为回文
    public boolean isPalindrome(String s) {
        // 双指针法，左指针从头，右指针从尾部向中间移动
        int left = 0, right = s.length() - 1;
        // 比较字符串左右两端的字符，直到左指针超过右指针
        while (left < right) {
            // 如果左右字符不相等，则不是回文
            if (s.charAt(left) != s.charAt(right)) return false;
            // 移动左右指针
            left++;
            right--;
        }
        // 如果没有发现不相等的字符，则是回文
        return true;
    }
}

题目2：132. 分割回文串 II

1.题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的 最少分割次数 。

示例 1：

1
2
3
输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

1
2
输入：s = "a"
输出：0

示例 3：

1
2
输入：s = "ab"
输出：1

提示：

  • 1 <= s.length <= 2000
  • s 仅由小写英文字母组成

2.题解

2.1 写法1-超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    int min = Integer.MAX_VALUE;
    List<String> path = new ArrayList<>();

    public int minCut(String s) {
        backtracking(s,0);
        return min;
    }

    public void backtracking(String s, int start) {
        if (start == s.length()) {
            min = path.size()-1 < min ? path.size()-1 : min;
            return;
        }

        for (int i = start; i < s.length(); i++) {
            String sub = s.substring(start, i + 1);
            if (isPalindrome(sub)) {
                path.add(sub);
                backtracking(s, i + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 2.9k 阅读时长 ≈ 5 分钟

回溯算法练习题

LeetCode链接：93. 复原 IP 地址

1.题目描述

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

1
2
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

  • 1 <= s.length <= 20
  • s 仅由数字组成

2.题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    // 定义一个列表 result，用于存储最终生成的所有合法的 IP 地址
    List<String> result = new ArrayList<>();

    // 主方法 restoreIpAddresses，输入一个字符串 s，返回所有可能的合法 IP 地址
    public List<String> restoreIpAddresses(String s) {
        // 如果字符串的长度不在有效范围内（4 到 12），直接返回空结果
        if (s.length() < 4 || s.length() > 12) return result;
        // 使用回溯算法生成所有可能的 IP 地址
        backtracking(s, new StringBuilder(), 0, 0);
        // 返回结果列表
        return result;
    }

    // 回溯算法方法 backtracking，构建有效的 IP 地址
    public void backtracking(String s, StringBuilder sb, int start, int level) {
        int len = s.length();

        // 当分割为 3 段时，处理剩下的最后一段
        if (level == 3) {
            // 如果剩余部分的长度超过 3 或 start 越界，则直接返回
            if (len - (start + 1) > 3 || start >= len) return;
            // 提取最后一段的字符串
            String sub = s.substring(start, len);
            // 检查这段字符串是否合法，如果合法则加入到结果中
            if (isValid(sub)) {
                sb.append(sub);  // 添加最后一段
                result.add(sb.toString());  // 将完整的 IP 地址添加到结果列表中
            }
            return;
        }

        // 从 start 开始，最多取 3 位字符
        for (int i = start; i < len && i - start < 3; i++) {
            // 提取从 start 到 i 的子字符串
            String sub = s.substring(start, i + 1);
            // 如果当前段不合法，直接返回
            if (!isValid(sub)) return;
            // 添加当前段到 StringBuilder，并添加一个 '.' 分隔符
            sb.append(sub).append(".");
            // 递归处理剩余的字符串
            backtracking(s, sb, i + 1, level + 1);
            // 回溯：删除刚才添加的字符，以便尝试其他组合
            sb.delete(start + level, sb.length());
        }
    }

    // 辅助方法 isValid，用于判断一个字符串是否为合法的 IP 地址段
    public boolean isValid(String s) {
        int len = s.length();
        
        // 如果字符串长度大于 1 且以 '0' 开头，则该段不合法（IP 段不能以 '0' 开头）
        if (len > 1 && s.charAt(0) == '0') return false;

        // 检查字符串中的字符是否全为数字
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c < '0' || c > '9') return false;
        }

        // 将字符串转换为整数，并检查是否在 0 到 255 的范围内
        int num = Integer.parseInt(s);
        return num >=0 && num <=255;
    }
}

3.练习

给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 "IPv4"；如果是有效的 IPv6 地址，返回 "IPv6"；如果不是上述类型的 IP 地址，返回 "Neither"。

有效的 IPv4 地址: 是x1.x2.x3.x4形式的 IP 地址，其中0 <= xi <= 255，且xi不能包含前导零。

  • 例如："192.168.1.1" 是有效的 IPv4 地址。
  • "192.168.1.01"、"192.168.1.00"、"192.168@1.1" 是无效的 IPv4 地址。

有效的 IPv6 地址: 是x1:x2:x3:x4:x5:x6:x7:x8形式的 IP 地址，其中1<=xi.length<=4，xi是一个十六进制字符串，可以包含数字、小写字母（从 ‘a’到 ‘f’）和大写字母（从 ‘A’到 ‘F’），在xi中允许前导零。

  • 例如："2001:0db8:85a3:0000:0000:8a2e:0370:7334" 是有效的 IPv6 地址。
  • "2001:db8:85a3::8a2e:0370:7334" 和 "02001:0db8:85a3:0000:0000:8a2e:0370:7334" 是无效的 IPv6 地址。

发表于 更新于 分类于 ， ， 阅读次数： Waline： 本文字数： 6.7k 阅读时长 ≈ 11 分钟

回溯算法练习题

题目1：77.组合

1.题目描述

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

1
2
输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n

2.题解

2.1 回溯算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    // 结果列表，用于存储所有组合
    List<List<Integer>> result = new ArrayList<>();
    // 当前路径，用于生成组合
    List<Integer> path = new ArrayList<>();

    // 主函数，生成1到n中选择k个数字的所有组合
    public List<List<Integer>> combine(int n, int k) {
        // 开始回溯，从数字1开始
        backtracking(n, k, 1);
        // 返回所有组合的结果
        return result;
    }

    // 回溯函数，n是范围的上限，k是组合的大小，startIndex是当前数字的起始索引
    public void backtracking(int n, int k, int startIndex) {
        // 如果当前路径的大小等于k，说明已经生成了一个合法的组合
        if (path.size() == k) {
            // 将当前路径的拷贝添加到结果列表中
            result.add(new ArrayList<>(path));
            // 退出当前回溯
            return;
        }

        // 从startIndex开始，遍历到n
        for (int i = startIndex; i <= n; i++) {
            // 将当前数字添加到路径中
            path.add(i);
            // 递归调用回溯函数，继续生成组合
            backtracking(n, k, i + 1);
            // 回溯，将最后一个数字从路径中移除
            path.remove(path.size() - 1);
        }
    }
}
  • 注意细节：
    • 细节1：每次递归的开始索引都是i+1，这样保证了不会重复，例如出现[3,4]和[4,3]的现象
    • 细节2：

2.2 回溯优化

  • 图解：

image-20240902220333770

  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    // 结果列表，用于存储所有组合
    List<List<Integer>> result = new ArrayList<>();
    // 当前路径，用于生成组合
    List<Integer> path = new ArrayList<>();

    // 主函数，生成1到n中选择k个数字的所有组合
    public List<List<Integer>> combine(int n, int k) {
        // 开始回溯，从数字1开始
        backtracking(n, k, 1);
        // 返回所有组合的结果
        return result;
    }

    // 回溯函数，n是范围的上限，k是组合的大小，startIndex是当前数字的起始索引
    public void backtracking(int n, int k, int startIndex) {
        // 如果当前路径的大小等于k，说明已经生成了一个合法的组合
        if (path.size() == k) {
            // 将当前路径的拷贝添加到结果列表中
            result.add(new ArrayList<>(path));
            // 退出当前回溯
            return;
        }

        // 优化：计算当前可以选择的数字的最大值
        // 减少无效递归的次数，确保路径中还可以添加足够的数字以满足组合的长度要求
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            // 将当前数字添加到路径中
            path.add(i);
            // 递归调用回溯函数，继续生成组合
            backtracking(n, k, i + 1);
            // 回溯，将最后一个数字从路径中移除
            path.remove(path.size() - 1);
        }
    }
}
  • 代码说明：
    • 已经选择的元素个数：path.size();
    • 还需要的元素个数为: k - path.size();
    • 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历

题目2：39.组合总和

1.题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

2.题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    // 存储所有符合条件的组合结果
    List<List<Integer>> result = new ArrayList<>();
    // 用于存储当前的组合路径
    List<Integer> path = new ArrayList<>();

    // 主方法，用于调用回溯算法并返回结果
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 从第一个元素开始进行回溯
        backtracking(candidates, target, 0, 0);
        return result; // 返回所有符合条件的组合结果
    }

    // 回溯方法，用于寻找所有和为 target 的组合
    public void backtracking(int[] candidates, int target, int sum, int start) { 
        // 如果当前路径的和等于目标值，将当前路径加入结果列表
        if (sum == target) {
            result.add(new ArrayList<>(path)); // 将当前路径的副本加入结果集
            return; // 回溯终止，返回上层调用
        }

        // 遍历候选数组，寻找下一步可能的组合
        for (int i = start; i < candidates.length && sum < target; i++) {
            path.add(candidates[i]); // 将当前元素加入路径
            // 递归调用回溯方法，继续寻找下一步组合
            backtracking(candidates, target, sum + candidates[i], i); 
            path.remove(path.size() - 1); // 回溯，移除最后一个加入的元素
        }
    }
}

题目3：40.组合总和II

1.题目描述

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

2.题解

写法1

1

题目4：216.组合总和III

1.题目描述

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

1
2
3
4
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

2.题解

2.1 写法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    // 存储所有满足条件的组合结果
    List<List<Integer>> result = new ArrayList<>();
    // 当前的组合路径
    List<Integer> path = new ArrayList<>();

    // 主方法：求和为n的k个数的所有组合
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 从数字1开始进行回溯
        backtracking(k, n, 1);
        // 返回结果列表
        return result;
    }

    // 回溯方法：生成符合条件的组合
    public void backtracking(int k, int n, int startIndex) {
        // 递归终止条件：当路径中的数字数量达到k时
        if (path.size() == k) {
            int sum = 0;
            // 计算路径中所有数字的总和
            for (int i = 0; i < k; i++) sum += path.get(i);
            // 如果总和等于目标值n，则将该路径加入结果列表
            if (sum == n) result.add(new ArrayList<>(path));
            return; // 终止当前递归
        }

        // 从startIndex开始遍历数字1到9
        for (int i = startIndex; i <= 9; i++) {
            path.add(i); // 将当前数字加入路径
            // 递归调用，将下一个数字加入路径，i+1确保每个数字只用一次
            backtracking(k, n, i + 1);
            path.remove(path.size() - 1); // 回溯，移除路径中的最后一个数字
        }
    }
}

2.2 优化1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    // 存储所有满足条件的组合结果
    List<List<Integer>> result = new ArrayList<>();
    // 当前的组合路径
    List<Integer> path = new ArrayList<>();

    // 主方法：求和为n的k个数的所有组合
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 从数字1开始进行回溯
        backtracking(k, n, 1);
        // 返回结果列表
        return result;
    }

    // 回溯方法：生成符合条件的组合
    public void backtracking(int k, int n, int startIndex) {
        // 递归终止条件：当路径中的数字数量达到k时
        if (path.size() == k) {
            int sum = 0;
            // 计算路径中所有数字的总和
            for (int i = 0; i < k; i++) sum += path.get(i);
            // 如果总和等于目标值n，则将该路径加入结果列表
            if (sum == n) result.add(new ArrayList<>(path));
            return; // 终止当前递归
        }

        // 优化后的循环：限制循环范围以减少不必要的遍历
        // 当path.size()已选择的数字数和剩余的k-path.size()个数字无法满足1-9的范围时，循环提前结束
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i); // 将当前数字加入路径
            // 递归调用，将下一个数字加入路径，i+1确保每个数字只用一次
            backtracking(k, n, i + 1);
            path.remove(path.size() - 1); // 回溯，移除路径中的最后一个数字
        }
    }
}

2.3 优化2（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    // 存储所有满足条件的组合结果
    List<List<Integer>> result = new ArrayList<>();
    // 当前的组合路径
    List<Integer> path = new ArrayList<>();

    // 主方法：求和为n的k个数的所有组合
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 初始化回溯，起始索引为1，总和为0
        backtracking(k, n, 1, 0);
        // 返回结果列表
        return result;
    }

    // 回溯方法：生成符合条件的组合
    public void backtracking(int k, int n, int startIndex, int sum) {
        // 递归终止条件：当路径中的数字数量达到k时
        if (path.size() == k) {
            // 如果当前路径的总和等于目标值n，则将路径加入结果列表
            if (sum == n) result.add(new ArrayList<>(path));
            return; // 终止当前递归
        }

        // 优化后的循环：限制循环范围以减少不必要的遍历
        // 当剩余的数字数量不足以组成所需的k个数字时，提前结束循环
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i); // 将当前数字加入路径
            //sum += i; // 更新当前路径的总和
            // 递归调用，将下一个数字加入路径，i+1确保每个数字只用一次
            backtracking(k, n, i + 1, sum + i);
            path.remove(path.size() - 1); // 回溯，移除路径中的最后一个数字
            //sum -= i; // 恢复总和为添加当前数字之前的值
        }
    }
}