Poison

491. Increasing Subsequences

发表于
Backtracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(resultList, path, nums, 0);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, Deque<Integer> path, int[] nums, int startIndex) {
        if (path.size() >= 2) {
            resultList.add(new ArrayList<>(path));
        }

        Set<Integer> set = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {
            if (i > startIndex && set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);

            if (path.isEmpty() || nums[i] >= path.getLast()) {
                path.add(nums[i]);
                dfs(resultList, path, nums, i + 1);
                path.removeLast();
            }
        }
    }
}

注意此题不能排序，导致同层去重时不能使用 nums[i] == nums[i - 1] 判断，所以引入了 Set 来判断重复。

Backtracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();
        dfs(resultList, path, nums, 0);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, Deque<Integer> path, int[] nums, int index) {
        if (index == nums.length) {
            if (path.size() >= 2) {
                resultList.add(new ArrayList<>(path));
            }
            return; // 此处不要忘记 return
        }

        // 当前元素与被选择的上一个元素相同时
        if (!path.isEmpty() && nums[index] == path.getLast()) {
            // 丢弃掉 选 -> 不选 这条路径，只进入 选 -> 选 这条路径
            path.add(nums[index]);
            dfs(resultList, path, nums, index + 1);
            path.removeLast();
        } else {
            // 当前元素与被选择的上一个元素不相同时，进入下一层的条件为当前元素大于等于之前选择的元素
            if (path.isEmpty() || nums[index] > path.getLast()) {
                path.add(nums[index]);
                dfs(resultList, path, nums, index + 1);
                path.removeLast();
            }

            dfs(resultList, path, nums, index + 1);
        }
    }
}

通过对每个元素进行选与不选来驱动搜索。因为本题元素无序，所以我们比较的元素为上一个被选择的元素而不是索引减去 1 的元素，而对于重复的组合，是因为当两个元素值相同时，’选 -> 不选’ 和 ‘不选 -> 选’ 这两条路径导致了最后组合的重复，那么当当前的元素与之前被选择的元素值相同时，我们丢弃掉 ‘选 -> 不选’ 这条路径，即可实现组合去重。

Reference

491. Increasing Subsequences