Leetcode: Permutations

46. Permutations

My Submissions

Total Accepted: 81411 Total Submissions: 239626 Difficulty: Medium

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

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Subscribe to see which companies asked this question

Hide Tags

 Backtracking

Show Similar Problems

BT problem:
Using the similar method as SUBSET. Composing the subsets by insertion.




//////////////////////////////////////////////

class Solution {

 public:

        void backTrac(vector<int>& nums, vector<vector<int>> &result, vector<vector<int>> &tmp, int i){

               if (i == 0){

                      vector<vector<int>> tmp1;

                      vector<int> vTmp;

                      vTmp.push_back(nums[i]);

                      tmp1.push_back(vTmp);

                      tmp = tmp1;

                      result = tmp;

                      return;

               }

               else{

                      backTrac(nums, result, tmp, i - 1);

                      

                      //insertion

                      vector<vector<int>> tmp1;

                      for (int m = 0; m<tmp.size(); m++){

                            for (int n = 0; n<=tmp[m].size(); n++){

                                   vector<int> vt;

                                   vt = tmp[m];

                                   vector<int>::iterator it = vt.begin();

                                   it = it + n;

                                   if (i == nums.size()) break;

                                   vt.insert(it, nums[i]);

                                   tmp1.push_back(vt);

                            }

                      }

                      tmp = tmp1;

                      result = tmp;

               }

        }

        vector<vector<int>> permute(vector<int>& nums) {

               vector<vector<int>> result, tmp;

               int i = nums.size() - 1;

               backTrac(nums, result, tmp, i);

               return result;

        }

 };