代码随想录算法训练营第二十九天| 491.递增子序列、46.全排列、47.全排列 II

491.递增子序列

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

解题思路：同层相同元素要跳过

java：

class Solution {List<List<Integer>> result=new ArrayList<>();List<Integer> path=new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTrace(nums,0);return result;}public void backTrace(int[] nums,int start){if(path.size()>1)result.add(new ArrayList(path));HashSet<Integer> hs = new HashSet<>();for(int i = start; i < nums.length; i++){if(!path.isEmpty() && path.get(path.size() -1 ) > nums[i] || hs.contains(nums[i]))continue;hs.add(nums[i]);path.add(nums[i]);backTrace(nums, i + 1);path.remove(path.size() - 1);}}
}

46.全排列

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

解题思路：只需要将每轮第一个访问跳过

java：

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used;public List<List<Integer>> permute(int[] nums) {if (nums.length == 0){return result;}used = new boolean[nums.length];permuteHelper(nums);return result;}private void permuteHelper(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]);permuteHelper(nums);path.removeLast();used[i] = false;}}
}

47.全排列 II

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

解题思路：同层的跳过

java：

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used;public List<List<Integer>> permuteUnique(int[] nums) {if (nums.length == 0){return result;}used = new boolean[nums.length];permuteHelper(nums);return result;}private void permuteHelper(int[] nums){if (path.size() == nums.length){result.add(new ArrayList<>(path));return;}HashSet<Integer> hs=new HashSet<>();for (int i = 0; i < nums.length; i++){if (used[i]||hs.contains(nums[i])){continue;}used[i] = true;hs.add(nums[i]);path.add(nums[i]);permuteHelper(nums);path.removeLast();used[i] = false;}}
}