我的方法一：递归

为了求长度n的所有组合，我们可以先得到n-1长度的所有组合，然后将第n个元素分别插入到每个组合的每个元素前后

步骤

获得n-1长度的所有组合subs;
然后遍历subs的每个组合sub，然后将n个数字依次插入到sub元素的每个位置上，获得n长度的所有组合；当然有n-1长度的组合有n个位置可以放

初始条件

边界条件

nums长度为0，直接返回空
nums长度为1，只有一个组合，即该数字

复杂度

时间复杂度：O(N2)，因为遍历每个数字是O(N)，每个数字插入到子组合中又需要O(N)，所以是O(N2)
空间复杂度：O(N)，递归隐式地使用了栈

代码

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        return permute(nums, nums.size());
    }

    vector<vector<int>> permute(vector<int>& nums, int n) {
        if(n == 0){
            vector<vector<int>> ret;
            return ret;
        }else if(n == 1){
            vector<vector<int>> ret;
            vector<int> sub;
            sub.push_back(nums[0]);
            ret.push_back(sub);
            return ret;
        }

        vector<vector<int>> ret;
        vector<vector<int>> subs = permute(nums, n-1);
        for(int i = 0; i<subs.size(); i++){
            vector<int>& sub = subs[i];
            for(int j = 0; j<=sub.size(); j++){
                vector<int> cur;
                for(int k = 0; k<j; k++){
                    cur.push_back(sub[k]);
                }
                cur.push_back(nums[n-1]);
                for(int k = j; k<sub.size(); k++){
                    cur.push_back(sub[k]);
                }
                ret.push_back(cur);
            }
        }
        return ret;
    }
};

我的方法二：动态规划

动态规划和递归的区别是，递归是从上到下，动态规划是从下到上。即递归是，为了求出f(n)，先求f(n-1)，依次类推；动态规划是为了求出f(n)，从f(1)开始求，一直求到f(n)；

步骤：

确认状态
1.1 最后一步
根据求到的n-1长度的组合结果，求出n长度的组合结果
1.2 子问题
n-1长度的组合结果
转移方程
f(n) = f(n-1) && 遍历f(n-1)并插入第n个数
初始条件和边界条件0
3.1 f(0)：空
3.2 f(1)：返回一个结果
3.2 当n==0或者n==1时，停止
计算顺序
f(0) f(1) ... f(n)

复杂度

时间复杂度：O(N2)，遍历n个长度的数O(N)，处理每个数，又需要O(N)
空间复杂度：O(N2)，即每个f需要O(N)的空间，一共需要N个f，所以是O(N2)
优化版空间复杂度：由于f(n)之和f(n-1)有关，所以n-1之前的结果可以不保存，所以“需要N个f”变为了“需要2个f”，所以是O(N)。

代码

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        if(nums.size() == 0){
            return vector<vector<int>>();
        }

        vector<vector<int>> ret1;
        vector<vector<int>> ret2;
        
        //f[0]
        vector<int> sub;
        sub.push_back(nums[0]);
        ret1.push_back(sub);

        vector<vector<int>>* fn = &ret1;
        vector<vector<int>>* fn_1 = &ret2;
        vector<vector<int>>* tmp = 0;

        //fn = fn_1 && ...
        for(int i = 1; i<nums.size(); i++){
            fn_1->clear();
            tmp = fn_1;
            fn_1 = fn;
            fn = tmp;

            //遍历fn_1
            for(int j = 0; j<fn_1->size(); j++){
                //遍历fn_1每个组合
                for(int k = 0; k<=(*fn_1)[j].size(); k++){
                    vector<int> sub;
                    for(int m = 0; m<k; m++){
                        sub.push_back((*fn_1)[j][m]);
                    }
                    sub.push_back(nums[i]);
                    for(int m = k; m<(*fn_1)[j].size();m++){
                        sub.push_back((*fn_1)[j][m]);
                    }
                    fn->push_back(sub);
                }
            }
        }

        return *fn;
    }
};