day29 打卡491.递增子序列 46.全排列 47.全排列 II

491.递增子序列

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

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

    private void backtracking(int[] nums, int startIndex) {
        if (path.size() > 1) {
            result.add(new ArrayList<>(path));
        }

        Set<Integer> set = new HashSet<>(); 
        for (int i = startIndex ; i<nums.length ; i++) {
            // 剪枝，当后一个节点小于path最后一个元素就不需要加入了
            if (!path.isEmpty() && nums[i] < path.get(path.size()-1)) {
                continue;
            }
            // 剪枝，每一层出现之前相同的就不需要再走着条路了
            if (set.contains(nums[i])) {
                continue;
            }

            set.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums, i+1);
            path.removeLast();
        }
    }
}

46.全排列

46题目链接

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

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

    private 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题目链接

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<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;
    }

    private void backtracking(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0 ; i<nums.length ; i++) {
            // 树层上去重
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
                continue;
            }

            // 已经取到的元素不需要再取了
            if (used[i]) {
                continue;
            }

            used[i] = true;
            path.add(nums[i]);
            backtracking(nums);
            used[i] = false;
            path.removeLast();
        }
    }
}