46. Permutations (DFS with recursion)

对46题一个解答的解释，希望能对其他同类型的backtracking的题目达到举一反三

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        //这里也可以不存int array的长度，只是后面就需要每次都自己算
        int len = nums.length;
        //新建一个空的二维ArrayList来存Integer的初始化方法为如下形态
        //重点要注意尖括号里面的List不能写成ArrayList，原因是里面为类型，并没有实例化，所以要一致
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        //int array to ArrayList<Integer> 可以自己手动下手，或者也可以用
        //List<Integer> choose = Arrays.asList(ArrayUtils.toObject(array));
        List<Integer> choose = new ArrayList<Integer>();
        for (int i : nums){
            choose.add(i);
        }
        helper(len, result, new ArrayList<Integer>(), choose);
        return result;    
    }
        //这里用void所以不需要返回值了，但是如果用了特定的类型，则即便返回null值也需要写上 return null;
    private void helper(int len, List<List<Integer>> ans, List<Integer> cur, List<Integer> choose){
        if(cur.size() == len){
        //假如这里不新建一个cur，之后对cur的改动会改变ans里面的cur值。所以需要新建另一个object，内容跟cur一模一样，但是却是两个object
            List<Integer> temp = new ArrayList<>(cur);
            ans.add(temp);
        }
        for(Integer ele: choose){
            cur.add(ele);
            List<Integer> temp = new ArrayList<>(choose);
            temp.remove(ele);
            helper(len, ans, cur, temp);
        //为了能使迭代逻辑成立，ele需要在cur中被移出
            cur.remove(ele);
        }
    }
}