Given a collection of distinct integers, return all possible permutations.
1. count==n, add tinylist to list;
2. iterate through the input array, if the int hasn‘t been added to the tinylist, add it to the tinylist, and continue dbp
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list=new ArrayList<>(); boolean[] bool=new boolean[nums.length]; findPermute(nums, list, new ArrayList<Integer>(), bool); return list; } public void findPermute(int[] nums, List<List<Integer>> list, List<Integer> tinyList, boolean[] bool){ if(tinyList.size()==nums.length){ list.add(new ArrayList(tinyList)); return; } for(int i=0;i<nums.length;i++){ if(!bool[i]){ bool[i]=true; tinyList.add(nums[i]); findPermute(nums, list, tinyList, bool); bool[i]=false; tinyList.remove(tinyList.size()-1); } } } }
可以不用bool去存储tinylist里是否包含该数字，直接判断tinylist.contains即可，就是会稍微比用bool存慢一点点，时间换空间
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list=new ArrayList<>(); findPermute(nums, list, new ArrayList<Integer>()); return list; } public void findPermute(int[] nums, List<List<Integer>> list, List<Integer> tinyList){ if(tinyList.size()==nums.length){ list.add(new ArrayList(tinyList)); return; } for(int i=0;i<nums.length;i++){ if(!tinyList.contains(nums[i])){ tinyList.add(nums[i]); findPermute(nums, list, tinyList); tinyList.remove(tinyList.size()-1); } } } }
注意，在back tracking的时候每次添加tinylist的时候都要新创建一个list加进去，要不然最后加进去的全是空的list！！（
list.add(new ArrayList(tinyList));）
leetcode 46-Permutation(medium)
原文：https://www.cnblogs.com/yshi12/p/9691868.html