LeetCode [46] Permutations

 46. Permutations

Medium

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; int n = nums.size(); if(!n) return res; bool used[n]; memset(used, false, n*sizeof(bool)); vector<int> cur; bt(nums, used, cur, 0, n, res); return res; } void bt(vector<int>& nums, bool used[], vector<int> cur, int len, int n, vector<vector<int>> &res){ if(n==len){ res.push_back(cur); }else{ for(int i=0; i<n; ++i){ if(!used[i]){ used[i] = true; cur.push_back(nums[i]); bt(nums, used, cur, len+1, n, res); cur.pop_back(); used[i] = false; } } } } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> ret; dfs(ret, nums, 0, nums.size()); return ret; } void dfs(vector<vector<int>> &ret, vector<int> &nums, int p, int n){ if(p==n){ ret.push_back(nums); }else{ for(int i=p; i<n; ++i){ swap(nums[p], nums[i]); dfs(ret, nums, p+1, n); swap(nums[p], nums[i]); } } } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { List<List<Integer>> lists; public List<List<Integer>> permute(int[] nums) { lists = new ArrayList<>(); dfs(nums.length, nums, new ArrayList<>(), new HashSet<>()); return lists; } void dfs(int n, int[] nums, List<Integer> list, Set<Integer> used){ if(list.size()==n){ lists.add(list); }else{ for(int i=0; i<n; ++i){ if(!used.contains(nums[i])){ List<Integer> newList = new ArrayList<>(list); newList.add(nums[i]); used.add(nums[i]); dfs(n, nums, newList, used); used.remove(nums[i]); } } } } }