代码随想录算法训练营第二十五天| 491.递增子序列* 46.全排列* 47.全排列 II

491.递增子序列?

代码随想录

视频讲解：回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列_哔哩哔哩_bilibili

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return ans;
    }

    public void backTracking(int[] nums, int startIndex) {
        if (list.size() > 1) {
            ans.add(new ArrayList<>(list));
        }
        HashSet<Integer> set = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {
            if (!list.isEmpty() && list.get(list.size() - 1) > nums[i] || set.contains(nums[i])) continue;
            set.add(nums[i]);
            list.add(nums[i]);
            backTracking(nums, i + 1);
            list.removeLast();
        }
    }
}

46.全排列?

代码随想录

视频讲解：组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列_哔哩哔哩_bilibili

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    HashSet<Integer> set = new HashSet<>();
    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums);
        return ans;
    }

    public void backTracking(int[] nums) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) continue;
            set.add(nums[i]);
            list.add(nums[i]);
            backTracking(nums);
            list.removeLast();
            set.remove(nums[i]);
        }
    }
}

47.全排列?II?

代码随想录

视频讲解：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II_哔哩哔哩_bilibili

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0) return new ArrayList<>();
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return ans;
    }

    public void backTracking(int[] nums) {
        if (list.size() == nums.length) {
            ans.add(new ArrayList<>(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
            if (used[i]) continue;
            used[i] = true;
            list.add(nums[i]);
            backTracking(nums);
            list.removeLast();
            used[i] = false;
        }
    }
}

难点：

used[i - 1] == false：这是最关键的部分。如果当前元素与前一个元素相同，并且前一个元素尚未被使用（即 used[i - 1] == false），这意味着我们正处于尝试将当前元素（nums[i]）放在前一个相同元素（nums[i - 1]）之前的情况。为了避免重复的排列，我们需要跳过这种情况。

如果 used[i - 1] == true，表示前一个相同的元素已经被使用在当前的排列中了，我们可以继续使用当前的元素，因为它会产生不同的排列。