算法|递增子序列、全排列、全排列 II

一、 491. 递增子序列

题目链接：https://leetcode.cn/problems/increasing-subsequences/

class Solution {
    private List<Integer> paths;
    private List<List<Integer>> result;
    private void backTracking(int[] nums, int startIndex) {
        if (paths.size() > 1) {
            result.add(new ArrayList<>(paths));
        }
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++){
            //递增判断
            if (!paths.isEmpty() && nums[i] < paths.get(paths.size() - 1)) continue;
            //树层去重
            if (hashSet.contains(nums[i])) continue;
            hashSet.add(nums[i]);
            paths.add(nums[i]);
            backTracking(nums, i + 1);
            paths.remove(paths.size() - 1);
        }
    }
    public List<List<Integer>> findSubsequences(int[] nums) {
        paths = new ArrayList<>();
        result = new ArrayList<>();
        backTracking(nums, 0);
        return result;
    }
}

二、 46. 全排列

题目链接：https://leetcode.cn/problems/permutations/

class Solution {
    private List<Integer> paths;
    private List<List<Integer>> result;
    private void backTracking(int[] nums, boolean[] uses) {
        if (paths.size() == nums.length) {
            result.add(new ArrayList<>(paths));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (uses[i]) continue;
            paths.add(nums[i]);
            uses[i] = true;
            backTracking(nums, uses);
            uses[i] = false;
            paths.remove(paths.size() - 1);
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        paths = new ArrayList<>();
        result = new ArrayList<>();
        boolean[] uses = new boolean[nums.length];
        Arrays.fill(uses, false);
        backTracking(nums, uses);
        return result;
    }
}

三、 47. 全排列 II

题目链接：https://leetcode.cn/problems/permutations-ii/

class Solution {
    private List<Integer> paths;
    private List<List<Integer>> result;
    private void backTracking(int[] nums, boolean[] uses) {
        if (paths.size() == nums.length) {
            result.add(new ArrayList<>(paths));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (uses[i]) continue;
            if (i > 0 && nums[i] == nums[i - 1] && !uses[i - 1]) continue;
            paths.add(nums[i]);
            uses[i] = true;
            backTracking(nums, uses);
            uses[i] = false;
            paths.remove(paths.size() - 1);
        }

    }
    public List<List<Integer>> permuteUnique(int[] nums) {
        paths = new ArrayList<>();
        result = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] uses = new boolean[nums.length];
        Arrays.fill(uses, false);
        backTracking(nums, uses);
        return result;
    }
}