Leet Code:Permutations.cpp

class Solution {
public:
    vector<vector<int> > result;
    vector<vector<int> > permute(vector<int> &num) {
        permute(num,0);
        return result;
    }
    
    void permute(vector<int>  &num,int index)
    {
        if(index==num.size())
            result.push_back(num);
        else   
            for(int i=index;i<num.size();++i)
            {
                swap(num[i],num[index]);
    
                permute(num,index+1);
                
                swap(num[i],num[index]);
            }
            
    }
};

给定一个序列abcd， 可能的排列情况如图所示：

进行排列时先把序列划分成两部分，第一个字符和剩余的n-1个字符，然后对剩余的n-1个字符进行全排列。

为了得到序列的全排列，第一个字符要分别为序列中的每一个字符，所以可以使用一个循环交换首字符，然后对后面n-1那一部分进行递归调用。这里时间上是一个深度优先搜索(DFS),搜索到叶节点之后往回回溯，得到的是依次递增的全排列。