全排列

 1vector<vector<int>> permute(vector<int>& nums)
 2{
 3    vector<vector<int>> res;
 4    res.reserve(factorial(nums.size()));
 5
 6    backTrack(nums, res, 0);
 7    return res;
 8}
 9
10void backTrack(vector<int>& nums, vector<vector<int>>& res, int first)
11{
12    if(first == nums.size())
13        res.push_back(nums);
14
15    for(int i = first; i < nums.size(); i++)
16    {
17        std::swap(nums[first], nums[i]);
18        backTrack(nums, res, first + 1);
19        std::swap(nums[first], nums[i]);
20    }
21}
22
23size_t factorial(size_t sz)
24{
25    size_t res;
26    for(int i = 0; i < sz; i++) res *= i;
27    return res;
28}

 1class Solution
 2{
 3public:
 4    std::vector<vector<int>> res;
 5    std::vector<int> path;
 6    void backTrack(vector<int>& nums, vector<bool> used)
 7    {
 8        // 终止条件
 9        if(path.size() == nums.size())
10        {
11            res.push_back(path);
12            return;
13        }
14
15        for(int i = 0; i < nums.size(); i++)
16        {
17            // 如果当前元素已经被使用过了
18            // 就直接跳过它
19            if(used[i])
20                continue;
21
22            // 将当前元素标记为“已使用”
23            used[i] = true;
24            path.push_back(nums[i]);
25            // 对下一个元素进行操作
26            backTrack(nums, used);
27            // 撤销所有操作
28            path.pop_back();
29            used[i] = false;
30        }
31    }
32
33    vector<vector<int>> permute(vector<int>& nums)
34    {
35        // 用来标记已使用的元素
36        std::vector<bool> used(nums.size(), false);
37        backTrack(nums, used);
38        return res;
39    }
40};