46. Permutations --------M

Given an array nums of distinct integers, return all the possible . You can return the answer in any order.
 
Example 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1]
Output: [[1]]
 
Constraints:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

A:

就是简单的， 对每一个新加入的值， 重复以前的permutation，并insert 到各个位置。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> curRes;
        if(nums.size()==0)
            return curRes;
        curRes.push_back(vector<int>{nums[0]});
        for(int i = 1;i<nums.size();i++){
            vector<vector<int>> next;
            for(auto &line : curRes){
                for(int j = 0; j<=line.size(); j++){
                    vector<int> newLine = line;
                    newLine.push_back(nums[i]); // add the new vaule
                    //swap last value with the j position
                    newLine[line.size()] = newLine[j]; //use swap instead of insert
                    newLine[j] = nums[i];                    
                    next.push_back(newLine);
                }
            }
            curRes = next;
        }
        return curRes;
    }
};

--------------4th--pass -----------------------------------

思路是这样的：   每次把start位置的字换成所有的可能，然后递归调用。就不用去特意copy List了。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        helper(nums, res,0);
        return res;
    }
private:
    void helper(vector<int>& nums,vector<vector<int>> & res, int start ){
        int n = nums.size();
        if(start >=n ){
            vector<int> tmp = nums;
            res.push_back(tmp);
        }
        for(int i =start; i< n; i++){
            swap(nums[start], nums[i]);
            helper(nums, res, start+1);
            swap(nums[start], nums[i]);
        }
    }
};

这里的关键点，不好理解的地方就是：
为什么第二遍可以直接写swap(A,start, i)
***************这里的关键是要想明白：after All permutation, A 又变回原来的形状了。********



 Learned:

二.遍历HashSet ---------这是一个新的 方法（看起来新，但其实还是旧的，哈哈）

Set set = new HashSet();
  for(int i=0;i<100;i++)  {
   set .add("123");
  }

for(Iterator it=set.iterator();it.hasNext())  {
   System.out.println(it.next());
  }