leetcode47，leetcode491，leetcode40，leetcode90，系列问题包你懂！！！Trie树对于排列问题、组合等结果集去重的应用

leetcode47. 全排列 II，leetcode491. 非递减子序列，leetcode40. 组合总和 II，leetcode90. 子集 II

题目

不过多赘述

思路

实际上这几题是相同的，都是求一个结果集合，然后集合中的元素不能重复。并且每一个元素都满足一定要求。
那么实际上，我们想一想，trie树就是一种很好的具有去重功能的数据结构，那么这些问题就都可以归结为建立一个trie树，然后从头读到叶子节点，然后对于具体问题就是看他的要求了，比如排列问题相当于没要求，非递减子序列则是要求trie树dfs过程元素一致单调不减，求和就是累计递归过程中节点的值与target值对比，子集则是递归过程中每读一个新节点我就存一次结果。
这么一看是不是通透了，那么我们举一个例子，这个例子是leetcode491. 非递减子序列，也是我思考出这一思路的题，下面将是我逐步优化代码的过程。注意第三版trie树的set还可以用map，这样甚至能记录一些其他属性比如每个节点上出现该数字的次数。

题解

// 第一版，这时候我是建立一个trie树，然后再遍历的
class Solution {
    // 这题用trie树解决，其实init时候可以边建立树边记录数据，不用再dfs，可以优化一下
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> subList = new ArrayList<>();
    int len = 0;

    public List<List<Integer>> findSubsequences(int[] nums) {
        Node dummy = new Node();
        // 别忘了初始化默认是0
        dummy.val = -101;
        dummy.subNode = new ArrayList<>();
        trieInit(dummy, nums, 0);
        dfs(dummy);
        return list;
    }

    public void dfs(Node root) {
        if (root == null) {
            return;
        }
        for(int i=0;i<root.subNode.size();i++) {
            subList.add(root.subNode.get(i).val);
            len++;
            if (len > 1) {list.add(new ArrayList<>(subList));}
            dfs(root.subNode.get(i));
            len--;
            subList.remove(subList.size() - 1);
        }
    }

    public void trieInit(Node root, int[] nums, int idx) {
        if (idx == nums.length) {return;}
        for(int i=idx;i<nums.length;i++) {
            if (!root.subNode.isEmpty() && root.subNode.get(root.subNode.size() - 1).val == nums[i]) {continue;}
            if (root.val > nums[i]) {continue;}
            boolean flag = false;
            for (int j=0;j<root.subNode.size();j++) {
                if (root.subNode.get(j).val == nums[i]) {
                    trieInit(root.subNode.get(j), nums, i + 1);
                    flag = true;
                    break;
                }
            }
            if (flag) {continue;}
            Node node = new Node();
            node.val = nums[i];
            node.subNode = new ArrayList<>();
            root.subNode.add(node);
            /*subList.add(nums[i]);
            len++;
            if (len > 1) {list.add(new ArrayList<>(subList));}*/
            trieInit(node, nums, i + 1);
            /*len--;
            subList.remove(subList.size() - 1);*/
        }
    }
}

class Node {
    List<Node> subNode;
    int val;
}
// 第二版，我将建立树和遍历树合为一起，一边建立一边读
class Solution {
    // 这题用trie树解决，其实init时候可以边建立树边记录数据，不用再dfs，可以优化一下
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> subList = new ArrayList<>();
    int len = 0;

    public List<List<Integer>> findSubsequences(int[] nums) {
        Node dummy = new Node();
        // 别忘了初始化默认是0
        dummy.val = -101;
        dummy.subNode = new ArrayList<>();
        trieInit(dummy, nums, 0);
        return list;
    }
    
    public void trieInit(Node root, int[] nums, int idx) {
        //if (idx == nums.length) {return;}
        for(int i=idx;i<nums.length;i++) {
            if (!root.subNode.isEmpty() && root.subNode.get(root.subNode.size() - 1).val == nums[i]) {continue;}
            if (root.val > nums[i]) {continue;}
            boolean flag = false;
            for (int j=0;j<root.subNode.size();j++) {
                if (root.subNode.get(j).val == nums[i]) {
                    trieInit(root.subNode.get(j), nums, i + 1);
                    flag = true;
                    break;
                }
            }
            if (flag) {continue;}
            Node node = new Node();
            node.val = nums[i];
            node.subNode = new ArrayList<>();
            root.subNode.add(node);
            subList.add(nums[i]);
            len++;
            if (len > 1) {list.add(new ArrayList<>(subList));}
            trieInit(node, nums, i + 1);
            len--;
            subList.remove(subList.size() - 1);
        }
    }
}

class Node {
    List<Node> subNode;
    int val;
}
// 第三版，我意识到不需要Node类来具体对应树的数据结构，可以在每个节点进到trieInit函数时候建立一个set，这样set就是记录trie树当前节点下的所有可能子节点了，并且是自带去重的，还不用for遍历子节点了
class Solution {
    // 这题用trie树解决，其实init时候可以边建立树边记录数据，不用再dfs，可以优化一下
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> subList = new ArrayList<>();

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

    public void trieInit(int[] nums, int idx) {
        // 子节点中的数字都有哪些
        Set<Integer> set = new HashSet<>();
        for(int i=idx;i<nums.length;i++) {
            if (!subList.isEmpty() && subList.get(subList.size() - 1) > nums[i]) {continue;}
            if (set.contains(nums[i])) {continue;}
            subList.add(nums[i]);
            set.add(nums[i]);
            if (subList.size() > 1) {list.add(new ArrayList<>(subList));}
            trieInit(nums, i + 1);
            subList.remove(subList.size() - 1);
        }
    }
}