491.递增子序列

491. 非递减子序列 - 力扣（LeetCode）
本题也是子集问题，问题在于不能排序，并且数组中含有重复数值，所以需要在数层去重，但是因为两个重复的元素不一定相邻，所以和组合的去重不同，需要新建一个set

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }

    public void backTracking(int[] nums, int startIndex) {
        if (path.size() >= 2) {
            result.add(new ArrayList<>(path));
        }
        Set<Integer> hs = new HashSet<>(); //存储数层遍历时使用过的值
        for (int i = startIndex; i < nums.length; i++) {
            //2种情况不符合条件，一是nums[i]小于最后值，二是树层中已经遍历过该值
            if (!path.isEmpty() && path.getLast() > nums[i] || hs.contains(nums[i])) {
                continue;
            }
            hs.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums, i + 1);
            path.removeLast();
        }
    }
}

46.全排列

46. 全排列 - 力扣（LeetCode）
全排列问题不需要startIndex参数，因为当选择了一个数后，前面的数还需要遍历，需要一个used数组存储在该树枝上遍历过的数值

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backTracking(nums);
        return result;
    }

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

47.全排列 II

47. 全排列 II - 力扣（LeetCode）
本题和组合以及子集去重原理相同，都是去除数层中的重复数值，树枝中重复元素不需要去重，但是只需要遍历没有使用过的数值

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.sort(nums);
        backTracking(nums);
        return result;
    }

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