LeetCode 46. Permutations

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

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解析：
给定一组无重复的数字集合，求解其全排列。
此题目跟Leetcode 39. Combination Sum类似，仍然采用回溯法，通过深度优先来获取所有的排列情况。但与前一个题目的不同在于返回结果中没有重复项，并且dfs中每次遍历是从头开始，而不是从上一层的下标开始。代码整体逻辑与前一个题目类似，只需做细小改动，具体代码如下：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> ans;
        int num_lens;
        num_lens = nums.size();
        if(nums.empty())
            return result;
        vector<bool> used(num_lens, false);
        dfs(nums, used, result, ans);
        return result;
    }
    void dfs(vector<int> &nums, vector<bool> &used, vector<vector<int>> &result, vector<int> &ans)
    {
        if(ans.size() == nums.size())
            result.push_back(ans);
        else if(ans.size() > nums.size())
            return;
        else
        {
            for(int i=0; i < nums.size(); i++)
            {
                if(!used[i])
                {
                    used[i] = true;
                    ans.push_back(nums[i]);
                    dfs(nums, used, result, ans);
                    ans.pop_back();
                    used[i] = false;
                }
            }
        }
    }
};