本文主要是介绍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();// 别忘了初始化默认是0dummy.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();// 别忘了初始化默认是0dummy.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);}}
}
这篇关于leetcode47，leetcode491，leetcode40，leetcode90，系列问题包你懂！！！Trie树对于排列问题、组合等结果集去重的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
