Permutations

This is a very interesting article on permutations.

http://wordaligned.org/articles/next-permutation

For this problem, permutations is basically switching all the elements. See below for more details.
Permutations
Given a collection of 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].

Idea: We start from the head element and will be exchange it with the other elements one by one while backtracking till the end.

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        int n = num.size();
       
        vector<vector<int>> ret;
        bt(ret, num,0,n-1);
       
        return ret;
    }
   
    void bt(vector<vector<int>> &r,  vector<int> num, int k, int n)
    {
        if (k==n)
        {
            r.push_back(num);
        }
        else
        {
            for (int i=k;i<=n;i++)
            {
                //switch num[i] and num[k]
                int tmp = num[i];
                num[i] = num[k];
                num[k] = tmp;
               
                bt(r,num, k+1,n);
            }
        }
    }
};

What if there are duplicates? We need to decide when to do the switches.

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > ret;
        int n = num.size();
        perm(num,0,n-1,ret);
        return ret;
    }
   
    bool swap(int k, int i, const vector<int> num){
        for (int j=k;j<i;j++){
            if (num[j]==num[i]){
                return false;
            }
        }
        return true;
    }
 
    void perm(vector<int> num, int k, int n, vector<vector<int>> &ret)
    {
        if (k==n)
        {
        ret.push_back(num);
        }
        else
        {  
            for (int i=k;i<=n;i++)
            {
                if (swap(k,i,num))
                {
                   int t = num[i];
                   num[i] = num[k];
                   num[k] = t;
           
                   perm(num, k+1,  n, ret);
       
                }
            }
        }
    }      
};