LintCode: 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.

Tags Expand 

Recursion

DFS solution:
Reference: https://siddontang.gitbooks.io/leetcode-solution/content/backtracking/permutation.html
----backTracking problem
similar like combination problem:
While in combination, we use start and n to record how many elements already count
Here we use a isValid bool vector to record elements counted
Time: O(n!)
Space: O(n)

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> > permutations; if(nums.size() == 0) return permutations; vector<int> temvec; vector<bool> isVisited(nums.size(), false); DFS(isVisited, temvec, permutations, nums); return permutations; } private: void DFS(vector<bool> &isVisited, vector<int> &temvec, vector<vector<int> > &permutations, vector<int> &nums){ if(temvec.size() == nums.size()) { permutations.push_back(temvec); return; } for(int i = 0; i < nums.size(); i++){ if(isVisited[i]) continue; isVisited[i] = true; temvec.push_back(nums[i]); DFS(isVisited, temvec, permutations, nums); temvec.pop_back(); isVisited[i] = false; } } };

Non recursive solution ---- swap
Reference:
http://tech-wonderland.net/blog/leetcode-permutations-i-and-ii.html
http://blog.csdn.net/morewindows/article/details/7370155
http://fisherlei.blogspot.ca/2012/12/leetcode-permutations-ii.html