最近刷了一波排列组合以及子集问题 主要学会理解for循环中 i 与 pos 以及level的这些变量的理解 这个可以从递归树来判别
#题目：排列
Given a collection of distinct 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], [3,2,1] ]
并不用考虑重复
主要是看 递归树图 排列树图 上代码：

public ArrayList<ArrayList<Integer>> Permutation(int[] nums){
		ArrayList<ArrayList<Integer>> arrs = new ArrayList<>();
		ArrayList<Integer> arr = new ArrayList<>();
		helper(nums,0,arr,arrs);
		return arrs;
	}
	/*
	 * 简单地说：就是第一个数分别以后面的数进行交换
	 *E．g：E = （a , b , c），则 prem（E）= a.perm（b,c）+ b.perm（a,c）+ c.perm（a,b）
	 *然后a.perm（b,c）= ab.perm（c）+ ac.perm（b）= abc + acb.依次递归进行
	 */
	
	public void helper(int[] nums,int pos,ArrayList<Integer> arr,ArrayList<ArrayList<Integer>> arrs){
		if(pos == nums.length){
			//这是正确的写法

			arr = new ArrayList<>();
			for (int i = 0; i < nums.length; i++) {
				arr.add(nums[i]);
			}
			arrs.add(arr);
		}else{
			/**
			 * 我觉得过程是这样的
			 * perm(a,b,c) = a+perm(b,c)(pos = 0 取出a) = 
			 */
			for (int i = pos; i < nums.length; i++) {    //pos表示

				swap(nums,i,pos); //pos表示当前数       

				helper(nums,pos+1,arr,arrs);    //当前pos位置确定，在pos位置后面继续全排列

				swap(nums,i,pos);     //还原到原来的数组

			}
		}
	}
	
	private  void swap(int[] nums,int i,int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}


#题目：子集
Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
并不用考虑重复
子集树图 子集树pos图 上代码：

	public ArrayList<ArrayList<Integer>> subsetByDfs(int[] nums){
		ArrayList<ArrayList<Integer>> arrs = new ArrayList<>();
		ArrayList<Integer> arr = new ArrayList<>();
		helperByDfs(nums,arrs,arr,0);
		return arrs;
	} 
	
	private void helperByDfs(int[] nums,ArrayList<ArrayList<Integer>> arrs,
			ArrayList<Integer> arr,int pos){
		arrs.add(new ArrayList<>(arr));
		for (int i = pos; i < nums.length; i++) {
			arr.add(nums[i]);
			helperByDfs(nums,arrs,arr,i+1);
			arr.remove(arr.size()-1);
		}	                                                           
	}


#题目：组合 Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
并不用考虑重复
组合树图 上代码：

	public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> arrs = new ArrayList<>();
        ArrayList<Integer> arr = new ArrayList<>();
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
			nums[i] = i+1;  
		}
        Dfs(nums,arrs,arr,0,k,0);
        return arrs;
    }
    
    public void Dfs(int[] nums,List<List<Integer>> arrs,List<Integer> arr,int level,int k,int pos){
    	if(level==k){
    		arrs.add(new ArrayList<>(arr));
    		return;
    	}

    	for (int i = pos; i < nums.length; i++) {
			arr.add(nums[i]);
			Dfs(nums, arrs, arr, level+1, k, i+1);
			arr.remove(arr.size()-1);
		}
    }