046 - Permutations

Permutations

Given a collection of numbers, 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], and [3,2,1].

Hide Tags

Backtracking

Hide Similar Problems

(M) Next Permutation (H) Permutations II (M) Permutation Sequence (M) Combinations

题目倒简单，穷尽各种组合就是了。

但是遇到一个怪异的问题，蓝色的部分，如果去掉，就会出问题。

调试发现，new出来的数组，居然有时候不会是全0？！

很奇怪，自己写了段代码试了一下，确实有这个情况发生，强制清零之后就没有问题了。

补一课：new 出来的东西，真的不一定会初始化的。。。

参考： default initialization, value initialization

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> rst;
        int sz = nums.size();
        if(sz)
        {
            vector<int> group;
            int used = 0;
            int* inuse = new int[sz];
            memset(inuse, 0, sz*sizeof(int));
            build(rst, group, nums, sz, inuse, used);
        }  
        return rst;
    }
private:
    void build(vector<vector<int>>& rst, vector<int>& group, vector<int> nums, int sz, int* inuse, int used)
    {
        for(int ii=0; ii<sz; ++ii)
        {
            if(0 == inuse[ii])
            {
                group.push_back(nums[ii]);
                inuse[ii]=1;
                used++;
               
                if(used==sz)
                    rst.push_back(group);
                else
                    build(rst, group, nums, sz, inuse, used);
               
                used--;
                inuse[ii]=0;
                group.pop_back();
            }
        }
    }
};

16 ms.