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

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

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) {
        return helper(nums,0);
    }
private:
    vector<vector<int>> helper(vector<int>& nums, int start){
        vector<vector<int>> res;
        if(start == nums.size()-1){
            res.push_back(vector<int>{nums[start]});
        }else{
            for(int j = nums.size()-1;j>=start; j--){
                swap(nums[start], nums[j]);// switch 
                for(auto &v : helper(nums, start+1)){
                    v.push_back(nums[start]);
                    res.push_back(v);
                }
                swap(nums[start], nums[j]);// switch back
            }
        }
        return res;
    }
    void swap(int &a, int &b){
        int c = a;
        a = b;
        b = c;
    }
};

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



 Learned:
 1: ArrayList  的addAll 函数，并不能真正的产生新的变量。而仅仅是把原本的变量的指针指过去而已。

二.遍历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());
  }