[LeetCode 46 47]Permutations I II

题目链接：permutations

相似题型：

1.[LeetCode 39&40] Combination Sum I & II

2.[LeetCode 78] Subsets

3.[LeetCode 90] Subsets II

4.[LeetCode 22] Generate Parentheses

5. [LeetCode 77] Combinations

import java.util.ArrayList;import java.util.List;/** * Given a collection of numbers, return all possible permutations.For example,[1,2,3] have the following permutations:[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. * */public class Permutations {//25 / 25 test cases passed.//Status: Accepted//Runtime: 244 ms//Submitted: 0 minutes ago//时间复杂度O(n!) 空间复杂度O(n)public List<List<Integer>> permutations = new ArrayList<List<Integer>>();public List<List<Integer>> permute(int[] num) {List<Integer> nums = new ArrayList<Integer>();for (Integer i : num) {nums.add(i);}permute(nums, new ArrayList<Integer>());return permutations;}public void permute(List<Integer> nums, List<Integer> permutation) {if(nums.size() == 0) {permutations.add(permutation);return;}for (int i = 0; i < nums.size(); i++) {List<Integer> list1 = new ArrayList<Integer>(nums);List<Integer> list2 = new ArrayList<Integer>(permutation);list2.add(nums.get(i));list1.remove(i);permute(list1, list2);}}public static void main(String[] args) {}}

题目链接：permutations-ii

import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * Given a collection of numbers that might contain duplicates, return all possible unique permutations.For example,[1,1,2] have the following unique permutations:[1,1,2], [1,2,1], and [2,1,1]. * */public class PermutationsII {//30 / 30 test cases passed.//Status: Accepted//Runtime: 301 ms//Submitted: 0 minutes ago//时间复杂度O(n!) 空间复杂度O(n)public List<List<Integer>> permutations = new ArrayList<List<Integer>>();public List<List<Integer>> permuteUnique(int[] num) {List<Integer> nums = new ArrayList<Integer>();Arrays.sort(num);for (Integer i : num) {nums.add(i);}permuteUnique(nums, new ArrayList<Integer>());return permutations;}public void permuteUnique(List<Integer> nums, List<Integer> permutation) {if(nums.size() == 0) {permutations.add(permutation);return;}int pre = Integer.MAX_VALUE;for (int i = 0; i < nums.size(); i++) {if(nums.get(i) == pre) {continue;}List<Integer> list1 = new ArrayList<Integer>(nums);List<Integer> list2 = new ArrayList<Integer>(permutation);list2.add(nums.get(i));pre = list1.remove(i);permuteUnique(list1, list2);}}public static void main(String[] args) {}}

，生活中若没有朋友，就像生活中没有阳光一样