46. Permutations

Given a collection ofdistinctnumbers, 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],
  [3,2,1]
]

S: backtrack O(n!)

Basic idea: permutation of A[1..n] equals to

A[1] + permutation of (A[1..n] - A[1])

A[2] + permutation of (A[1..n] - A[2])

...

A[n] + permutation of (A[1..n] - A[n]).

对于固定的A[i], 递归地求A[i+1]..A[n]的permutation，通过swap实现A[1..n] - A[i], 避免额外空间存储已访问过的数字

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        dfs(nums, 0, result);
        return result;
    }

    void dfs(vector<int>& nums, int startPos, vector<vector<int>>& result) {
        if (startPos == nums.size()) {
            result.push_back(nums);
            return;
        }
        for (int i = startPos; i < nums.size(); ++i) {
            swap (nums[startPos], nums[i]);
            dfs(nums, startPos + 1, result);
            swap (nums[startPos], nums[i]);

        }
    }

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2]have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

S: sort + recursion O(n!)

只要有重复数组多半要排序。因为有重复，不能再backtrack

每次要保证start..n是排好序的，否则会出现重复。swap back会破坏下一层的排序

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        dfs(nums, 0, result);
        return result;
    }

    void dfs(vector<int> nums, int startPos, vector<vector<int>>& result) {
        if (startPos == nums.size()) {
            result.push_back(nums);
            return;
        }
        for (int i = startPos; i < nums.size(); ++i) {
            if (i == startPos || nums[i] != nums[startPos]) {  //重点！判重，不再backtrack nums
                swap (nums[startPos], nums[i]);
                dfs(nums, startPos + 1, result);
            }
        }
    }

31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3→1,3,2
3,2,1→1,2,3
1,1,5→1,5,1
S: find pattern O(n^n)

从后往前，找到最大的i满足nums[i]之后有比nums[i]大的数，交换两数后，对i之后的数排序

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        for (int i = n - 2; i >= 0; --i) {  //从后往前找
            for (int j = n - 1; j > i; --j) {  //同样从后往前找，最小的满足条件的j一定在最后
                if (nums[j] > nums[i]) {
                    swap(nums[i], nums[j]);                                 
                    sort(nums.begin() + i + 1, nums.end());
                    return;
                }
            }
        }
        reverse(nums.begin(), nums.end());
    }
};