Lintcode (15) Permutations

Given a list of numbers, return all possible permutations.

Have you met this question in a real interview? 

Yes

Example

For nums = [1,2,3], the permutations are:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Challenge

Do it without recursion.

这里用到了backtracking, 思路：

在第k个位置，除去已经push上去的前k-1个元素外，遍历其他元素，push到解上，并搜索k+1个位子。时间复杂度是n!, 单实际上会多出一个o(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 25 26 27 28 29 30 31

class Solution { public: /** * @param nums: A list of integers. * @return: A list of permutations. */ vector<vector<int> > permute(vector<int> nums) { // write your code here vector< vector<int> > result; if (nums.empty()) return result; vector<int> solution; bfs(result, solution, nums, 0); } void bfs(vector< vector<int> >& result, vector<int>& solution, vector<int>& nums, int level){ if (level == nums.size()){ result.push_back(solution); return; } for (int i=0; i<nums.size(); i++){ if (std::find(solution.begin(), solution.end(), nums[i])!=solution.end()) continue; solution.push_back(nums[i]); bfs(result, solution, nums, level+1); solution.pop_back(); } } };

为了去掉多余的搜索时间，用记忆化搜索，这样就会把o(i)变成o(1),其实快不了多少。。。图个心理舒服lol

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 30 31 32 33 34 35

class Solution { public: /** * @param nums: A list of integers. * @return: A list of permutations. */ vector<vector<int> > permute(vector<int> nums) { // write your code here vector< vector<int> > result; if (nums.empty()) return result; vector<int> solution; vector<bool> visited(nums.size(), false); dfs(result, solution, nums, 0, visited); } void dfs(vector< vector<int> >& result, vector<int>& solution, vector<int>& nums, int level, vector<bool>& visited){ if (level == nums.size()){ result.push_back(solution); return; } for (int i=0; i<nums.size(); i++){ if (visited[i]) continue; solution.push_back(nums[i]); visited[i]=true; dfs(result, solution, nums, level+1,visited); solution.pop_back(); visited[i]=false; } } };