C/C++全排列函数

C++中有全排列函数next_permutation，前提是数据必须有序，因此先对其进行排序，再使用该函数:

vector<vector<int>> permute(vector<int>& nums)
{
      vector<vector<int>> result;
      sort(nums.begin(),nums.end());
      result.push_back(nums);
      while (next_permutation(nums.begin(), nums.end()))
      {
        result.push_back(nums);
      }
      return result;
}

全排列的深度优先（DFS）实现

//全排列的深度优先（DFS）实现
void dfs(vector<int>& nums, map<int, int>& selected, int index,vector<int>& oneresult, vector<vector<int>>&result)
{
    if (index == nums.size())                           //排列完一次
    {
        result.push_back(oneresult);                    //本次结果加入最终结果
        return;
    }
    for (int i = 0; i < nums.size(); i++)               //对所有数据进行遍历
    {
        if (selected[i] != 0)                           //若已经选择过则跳过
            continue;
        //这里使用人工方式进行回溯完全是因为函数参数使用的是引用，
        //使用引用的方式是为了减少递归中参数复制导致时间的浪费。
        selected[i] = 1;                                //添加选中标识
        oneresult.push_back(nums[i]);                   //本元素加入本次结果中
        dfs(nums, selected, index + 1, oneresult, result);  //下一次遍历
        selected[i] = 0;                                //清除选中标识
        oneresult.pop_back();                           //本元素出本次结果
    }
}