Permutations I
Given a collection of distinct 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].
回溯法
思路
与subset不同的是对于数组[1,2,3] [2,1,3]和[2,3,1]等都算在排列里, 所以我们递归的的起始点不再是i+1, 而是每次都从0 开始.
但是由于每次都从0开始就没法知道是否要访问的下一个数之前有没有被用过, 所以这里用一个Boolean数组来存储每一个点的访问情况复杂度
时间O(n!) 空间栈 O(n!)
代码
public List
> permute(int[] nums) { List
> res= new ArrayList
>(); if (nums == null || nums.length == 0) { return res; } List tem = new ArrayList (); Arrays.sort(nums); boolean[] visit = new boolean[nums.length]; helper(nums, visit, res, tem); return res;}public void helper(int[] nums, boolean[] visit, List
> res, List tem) { if (tem.size() == nums.length) { res.add(new ArrayList (tem)); return; } for (int i = 0; i < nums.length; i++) { if (visit[i] == true) { continue; } visit[i] = true; tem.add(nums[i]); helper(nums, visit, res, tem); tem.remove(tem.size() - 1); visit[i] = false; }}
Permutations II
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].
回溯法
思路
与I不同的是这里允许了重复的元素 ,所以如果当前访问元素与之前元素相同而之前的元素没有访问过 说明相似的情况已经出现过 要避免再出现
复杂度
时间O(n!) 空间栈 O(n!)
代码
public List
> permuteUnique(int[] nums) { List
> res= new ArrayList
>(); if (nums == null || nums.length == 0) { return res; } List tem = new ArrayList (); Arrays.sort(nums); boolean[] visit = new boolean[nums.length]; helper(nums, visit, res, tem); return res;}public void helper(int[] nums, boolean[] visit, List
> res, List tem) { if (tem.size() == nums.length) { res.add(new ArrayList (tem)); return; } for (int i = 0; i < nums.length; i++) { if (visit[i] == true) { continue; } if (i != 0 && nums[i] == nums[i - 1] && !visit[i - 1]) { continue; } visit[i] = true; tem.add(nums[i]); helper(nums, visit, res, tem); tem.remove(tem.size() - 1); visit[i] = false; } }