标签： 回溯

目标

给你一个由正整数组成的数组 nums 和一个 正 整数 k 。

如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

示例 1：

输入：nums = [2,4,6], k = 2
输出：4
解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。

示例 2：

输入：nums = [1], k = 1
输出：1
解释：数组 nums 中的美丽数组有：[1] 。
可以证明数组 [1] 中只存在 1 个美丽子集。

说明：

• 1 <= nums.length <= 18
• 1 <= nums[i], k <= 1000

思路

返回数组的美丽子序列个数，美丽指子序列中任意两个元素的差的绝对值不等于 k。

由于数组长度不大，可以回溯枚举子序列，并针对每一子序列，两两比较，判断差的绝对值是否等于 k。

更好的处理方法是使用哈希表记录元素的出现次数，回溯枚举子序列时直接判断当前元素加减 k 的绝对值是否存在于哈希表中。

代码

/**
 * @date 2025-03-07 0:09
 */
public class BeautifulSubsets2597 {

    public int beautifulSubsets(int[] nums, int k) {
        return dfs(0, new ArrayList<>(), nums, k);
    }

    public int dfs(int index, List<Integer> path, int[] nums, int k) {
        if (index == nums.length) {
            return path.size() > 0 ? 1 : 0;
        }
        int res = 0;
        res += dfs(index + 1, path, nums, k);
        for (Integer num : path) {
            if (Math.abs(num - nums[index]) == k) {
                return res;
            }
        }
        path.add(nums[index]);
        res += dfs(index + 1, path, nums, k);
        path.remove(path.size() - 1);
        return res;
    }

}

性能

目标

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

示例 1：

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

示例 2：

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

说明：

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

思路

返回将字符串划分为回文子串的所有可能方案。

定义 dp[i] 表示将前 i + 1 个字符划分为回文子串的所有可能方案。dp[i] 可以取 dp[i - 1] 每种方案的最后一或两个回文，判断能否与当前字符合并成新的回文。

代码

/**
 * @date 2025-03-01 20:16
 */
public class Partition131 {

    public List<List<String>> partition(String s) {
        int n = s.length();
        List<List<String>>[] dp = new List[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new ArrayList<>();
        }
        char[] chars = s.toCharArray();
        dp[0].add(new ArrayList<>());
        dp[0].get(0).add((String.valueOf(chars[0])));
        for (int i = 1; i < n; i++) {
            dp[i] = new ArrayList<>();
            for (List<String> list : dp[i - 1]) {
                // 首先将单个字符加入
                List<String> tmp = new ArrayList<>(list);
                tmp.add(String.valueOf(chars[i]));
                dp[i].add(tmp);
                String cur = String.valueOf(chars[i]);
                // 判断能与最后一个回文合并成新的回文
                if (list.get(list.size() - 1).equals(cur)) {
                    tmp = new ArrayList<>(list.subList(0, list.size() - 1));
                    tmp.add(list.get(list.size() - 1) + cur);
                    dp[i].add(tmp);
                }
                // 判断能否与后两个回文合并成新的回文
                if (list.size() > 1 && list.get(list.size() - 2).equals(cur)) {
                    tmp = new ArrayList<>(list.subList(0, list.size() - 2));
                    tmp.add(list.get(list.size() - 2) + list.get(list.size() - 1) + cur);
                    dp[i].add(tmp);
                }
            }
        }
        return dp[n - 1];
    }

}

性能

时间复杂度 O(n * 2^n)，假设每个字符之间都有一个逗号，考虑选或不选共有 2^(n - 1) 种划分。前 i + 1 个 字符有 2^i 种划分， 等比数列求和得到 2^n - 1。

目标

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

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

示例 2：

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

说明：

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

思路

返回数组不重复的全排列。

依次枚举第 i 个位置的可选元素，不含重复元素的全排列个数为 n!，收集结果复杂度为 O(n)。重复排列的处理与 与 90.子集II 类似，先排序数组，在每个位置枚举元素时，直接跳过后续相同的元素。

代码

/**
 * @date 2025-02-06 8:41
 */
public class PermuteUnique47 {

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        boolean[] visited = new boolean[n];
        List<Integer> path = Arrays.asList(new Integer[n]);
        dfs(0, nums, visited, path, res);
        return res;
    }

    public void dfs(int index, int[] nums, boolean[] visited, List<Integer> path, List<List<Integer>> res) {
        int n = nums.length;
        if (index == n) {
            List<Integer> permute = new ArrayList<>(path);
            res.add(permute);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (visited[i] || (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            path.set(index, nums[i]);
            dfs(index + 1, nums, visited, path, res);
            visited[i] = false;
        }
    }

}

性能

目标

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

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

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

示例 1:

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

示例 2:

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

说明:

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

思路

有一个数组 candidates，用 candidates 中的元素值组成目标值 target，返回每种组合的元素列表。数组中的每个元素在每种组合中只能使用一次。

考虑是否选择某个元素，可能的组合有 2^n 种。但是题目有条件限制，要求组合元素值之和等于target，那么如果组合的和大于 target 可以提前返回。因此可以将 candidates 从小到大排序，回溯。关键是如何去除重复组合，对于相同的元素，只关心取的个数，因此如果不选某个元素，后续相同的元素也都不能选。

代码

/**
 * @date 2025-01-26 15:24
 */
public class CombinationSum40 {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, 0, target, candidates, path, res);
        return res;
    }

    public void dfs(int index, int sum, int target, int[] candidates, List<Integer> path, List<List<Integer>> res) {
        if (sum == target) {
            List<Integer> tmp = new ArrayList<>(path);
            res.add(tmp);
            return;
        }
        if (index == candidates.length || sum > target) {
            return;
        }
        int cur = candidates[index];
        path.add(cur);
        dfs(index + 1, sum + cur, target, candidates, path, res);
        path.remove(path.size() - 1);
        index++;
        // 如果不选当前的值，也同样不选后续所有相同的值
        // 对于相同的值，只考虑选了几个，如果这里不跳过，就会出现重复
        // 比如有4个相同的值，选 选 不选 不选，如果允许后续再次选择，就会出现
        // 选 不选 不选 选、
        // 选 不选 选 不选
        // 不选 选 选 不选、
        // 不选 选 不选 选、
        // 不选 不选 选 选、
        while (index < candidates.length && cur == candidates[index]) {
            index++;
        }
        dfs(index, sum, target, candidates, path, res);
    }
}

性能