给出一组数字,返回该组数字的所有排列
例如:
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
(以数字在数组中的位置靠前为优先级,按字典序排列输出。)
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
(以数字在数组中的位置靠前为优先级,按字典序排列输出。)
数据范围:数字个数
要求:空间复杂度 ,时间复杂度
[1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
[1]
[[1]]
// 解法二 ArrayList<ArrayList<Integer>> res2 = new ArrayList<>(); public ArrayList<ArrayList<Integer>> permute2(int[] num) { permutation(num, 0); return res2; } public void permutation(int[] num, int start) { if(start == num.length - 1) { ArrayList<Integer> list = new ArrayList<>(); for (int i = 0; i < num.length; i++) { list.add(num[i]); } res2.add(list); } for (int i = start; i < num.length; i++) { swap(num, i, start); permutation(num, start + 1); swap(num, i, start); } } public void swap(int[] num, int i, int j) { int temp; temp = num[i]; num[i] = num[j]; num[j] = temp; }
class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > res; permutation(res,num,0); return res; } void permutation(vector<vector<int> > &res,vector<int> &num,int s) { if(s == num.size()-1) res.push_back(num); else{ for(int i=s;i<num.size();i++) { swap(num[s],num[i]); permutation(res,num,s+1); swap(num[s],num[i]); } } } };
/** * 46. Permutations * @author Jacob * 题意:求数组的全排列 */ public class Demo1 { ArrayList<ArrayList<Integer>> res; public ArrayList<ArrayList<Integer>> permute(int[] nums) { res = new ArrayList<ArrayList<Integer>>(); if (nums == null || nums.length < 1) return res; //对数组元素进行从小到大排序 Arrays.sort(nums); ArrayList<Integer> list = new ArrayList<Integer>(); solve(list, nums); return res; } private void solve(ArrayList<Integer> list, int[] nums) { if (list.size() == nums.length) { res.add(new ArrayList<Integer>(list)); return; } for (int i = 0; i < nums.length; i++) { if (!list.contains(nums[i])) { list.add(nums[i]); solve(list, nums); list.remove(list.size() - 1); } } } }
import java.util.*; public class Solution { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); ArrayList<Integer> ls = new ArrayList<>(); public ArrayList<ArrayList<Integer>> permute(int[] num) { int[] used = new int[num.length]; dfs(num,used); return res; } private void dfs(int[] a,int[] used) { if(ls.size() == a.length) { res.add(new ArrayList<>(ls)); return; } for(int i = 0; i < a.length; i++) { if(used[i] == 1) continue; used[i] = 1; ls.add(a[i]); dfs(a,used); used[i] = 0; ls.remove(ls.size()-1); } } }
做烂了的回溯
class Solution { public: void dfs(int cur, vector<int> &tmp, vector<int> &taken, vector<int> &num, vector<vector<int> > &res){ int n = num.size(); if(tmp.size() == n){res.push_back(tmp);return;} for(int i = 0; i < n; i++){ if(!taken[i]){ taken[i] = 1; tmp.push_back(num[i]); dfs(i+1, tmp, taken, num, res); tmp.pop_back(); taken[i] = 0; } } } vector<vector<int> > permute(vector<int> &num) { vector<int> tmp; vector<int> taken(num.size(), 0); vector<vector<int> > res; dfs(0, tmp, taken, num, res); return res; } };
递归 + 回溯 不回溯的话num还停留在上一次递归排列的状态,可能会导致出现漏排的情况
时间复杂度:O(n!) 空间复杂度:O(n) 递归栈的深度
还有注意添加排列好的num时使用深拷贝
import copy class Solution: def recursion(self, num, res, index): if index == len(num) - 1: res.append(copy.deepcopy(num)) else: for i in range(index, len(num)): temp = num[i] num[i] = num[index] num[index] = temp self.recursion(num, res, index+1) temp = num[i] num[i] = num[index] num[index] = temp def permute(self , num: List[int]) -> List[List[int]]: num.sort() res = [] self.recursion(num, res, 0) return res
import java.util.*; ## 经典回溯 public class Solution { List<Integer> list = new ArrayList<>(); ArrayList<ArrayList<Integer>> result = new ArrayList<>(); public ArrayList<ArrayList<Integer>> permute(int[] num) { Arrays.sort(num); dfs(num,list); return result; } private void dfs(int[] num,List<Integer> list){ if(list.size() == num.length){ result.add(new ArrayList<>(list)); return; } for(int i = 0; i < num.length; i ++){ if(list.contains(num[i])){ continue; } list.add(num[i]); dfs(num,list); list.remove(list.size() - 1); } } }
class Solution { public: vector<vector<int> > permute(vector<int> &num) { // 时间复杂度O(N!),空间复杂度O(N!) vector<vector<int>> res; vector<int> path; sort(num.begin(), num.end()); recursion(num, path, res); return res; } void recursion(vector<int> &num, vector<int> &path, vector<vector<int>> &res) { if (num.empty()) { res.push_back(path); return; } for (int i = 0; i < num.size(); ++i) { path.push_back(num[i]); vector<int> tmp(num); // 拷贝一份,删除path中加入的num[i] tmp.erase(tmp.begin() + i); recursion(tmp, path, res); path.pop_back(); } } };
class Solution { public: void pushVec(vector<int> num, int index){ per.push_back(num); for(int i = index; i < num.size()-1; ++ i){ for(int j = i+1; j < num.size(); ++ j){ swap(num[i],num[j]); pushVec(num,i+1); swap(num[i],num[j]); } } } vector<vector<int> > permute(vector<int> &num) { pushVec(num,0); return per; } private: vector<vector<int> > per; };
class Solution { public: void dfs(vector<int> &num,vector<vector<int>> &res,int begin) { if(begin == num.size()) res.push_back(num); for(int i=begin;i<num.size();i++) { swap(num[i],num[begin]); dfs(num,res,begin+1); swap(num[i],num[begin]); } } vector<vector<int> > permute(vector<int> &num) { vector<vector<int>> res; if(num.size()==0) return res; sort(num.begin(),num.end()); dfs(num,res,0); return res; } };
class Solution { public: //next_permutation:会取得[first,last)所标识之序列的下一个排列组合 //如果没有下一个排列组合,便返回false,否则返回true。 vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > res; sort(num.begin(), num.end()); do { res.push_back(num); } while (next_permutation(num.begin(),num.end())); return res; } };
class Solution { void permutation(vector<vector<int> >&ans,vector<int>& num,int l) { if(l == num.size()-1) ans.push_back(num); else { for(int i=l;i<num.size();i++) { swap(num[l],num[i]); permutation(ans,num,l+1); swap(num[l],num[i]); } } } public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int> > ans; permutation(ans,num,0); return ans; } };
public ArrayList<ArrayList<Integer>> permute (int[] num) { ArrayList<ArrayList<Integer>> ans=new ArrayList<>(); ArrayList<Integer> list=new ArrayList<>(); build(num,ans,list); return ans; } public void build(int[] num,ArrayList<ArrayList<Integer>> ans,ArrayList<Integer> list){ if(list.size()==num.length){ //截至条件(终止条件) ans.add(new ArrayList<>(list)); } for(int i=0;i<num.length;i++){ if(list.contains(num[i])){ //因为这个题没有重复的数字, 所以当list中已经有了这个数字,那就剪枝 continue; } list.add(num[i]); build(num,ans,list); list.remove(list.size()-1); } }
class Solution { public: vector<vector<int> > permute(vector<int> &num) { vector<vector<int>> res; vector<int> ans; recursion(num, ans, res); return res; } void recursion(vector<int> vec, vector<int> &ans, vector<vector<int>> &res){ if(vec.size()==1){ ans.push_back(vec[0]); res.push_back(ans); ans.pop_back(); return; } for(int i : vec){ ans.push_back(i); vector<int> newvec; for (int j : vec){ if(i!=j) newvec.push_back(j); } recursion(newvec, ans, res); ans.pop_back(); } } };
class Solution: def permute(self , num: List[int]) -> List[List[int]]: n = len(num) res_all = [] # all result res = [] # result def dfs(res): # dfs函数是permute函数的闭包函数 if len(res) == n: res_all.append(res[:]) # res[:]可以开辟新内存存储结果,防止被下面的res.pop()影响 for i in range(n): if num[i] not in res: res.append(num[i]) dfs(res) res.pop() dfs(res) return res_all
public class Solution { ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>(); int len; public ArrayList<ArrayList<Integer>> permute(int[] num) { if(num==null||num.length==0) return ans; //先对数组排序保证最后返回的结果是按字典排序输出 Arrays.sort(num); len = num.length; //创建一个数组记录已经加入数组的元素 boolean[] isVisi = new boolean[len]; //递归添加元素 dfs(num,isVisi,new ArrayList()); return ans; } void dfs(int[] num,boolean[] vis,ArrayList<Integer> ls){ if(ls.size()==len){ ans.add(new ArrayList(ls)); return; } for(int i = 0;i<len;i++){ if(vis[i]) continue; vis[i] = true; ls.add(num[i]); dfs(num,vis,ls); //回溯 vis[i] = false; ls.remove(ls.size()-1); } } }
class Solution { public: vector<vector<int>>res; vector<vector<int> > permute(vector<int> &num) { sort(num.begin(),num.end()); vector<int>track; backtrack(num,track); return res; } void backtrack(vector<int>&num,vector<int>&track){ if(track.size()==num.size()){ res.push_back(track); return; } for(int i=0;i<num.size();++i){ if(count(track.begin(),track.end(),num[i])){ continue; } track.push_back(num[i]); backtrack(num,track); track.pop_back(); } } };