46. Permutations

My solution will erase and insert elements in arrays which is slow.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> permute(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      if (nums.size() == 0) return res;  
6:      vector<int> sol;  
7:      helper(nums, sol, res);  
8:      return res;  
9:    }  
10:    void helper(vector<int> &nums, vector<int> &sol, vector<vector<int>> &res) {  
11:      if (nums.size() == 0) {  
12:        res.push_back(sol);  
13:        return;  
14:      }  
15:      for (int i = 0; i < nums.size(); i++) {  
16:        int num = nums[i];  
17:        sol.push_back(num);  
18:        nums.erase(nums.begin()+i);  
19:        helper(nums, sol, res);  
20:        sol.pop_back();  
21:        nums.insert(nums.begin()+i, num);  
22:      }  
23:    }  
24:  };  

A better way is to use the invariant that nums[0...begin] has been permuted.

1:  class Solution {  
2:  public:  
3:    vector<vector<int>> permute(vector<int>& nums) {  
4:      vector<vector<int>> res;  
5:      helper(nums, 0, res);  
6:      return res;  
7:    }  
8:    void helper(vector<int> &nums, int begin, vector<vector<int>> &res) {  
9:      if (begin >= nums.size()) {  
10:        res.push_back(nums);  
11:        return;  
12:      }  
13:      // invariant is [0, begin-1] has been permuted  
14:      for (int i = begin; i < nums.size(); i++) {  
15:        swap(nums[begin], nums[i]);  
16:        helper(nums, begin+1, res);  
17:        swap(nums[i], nums[begin]);  
18:      }  
19:    }  
20:  };