回溯

回溯三步曲

1. 回溯函数终止条件
2. 回溯搜索的遍历过程

   for () {
       加入元素;
       backtracking(···); // 递归
       回溯（返回元素）；
   }

3. 回溯函数返回值以及参数

认识回溯算法：
回溯算法就是暴力求解的过程，当我们拿到[1,2,3]我们就尝试拿一个1，然后递归自己，再次从[1,2,3]中尝试拿数，1已经拿过了，所以下一步我们拿2，再次递归自己拿数3，这时就满足题目要求了。
然后回退3，手里剩下1，2，再回退2，手里剩下1，此时之前已经拿过1，2了，所以这时for循环到了3，我们拿3，再递归自己，只剩下2，就组成了1，3，2

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入： nums = [1,2,3]
输出： [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

1. 第一步，回溯算法的终止条件是什么呢？就是长度和nums数组长度一致时，就说明得到了一个结果。
2. 遍历过程：
   就是在数组中找之前没选过的数字，为了达到这个目的我们需要哈希表辅助，这里我们可以自己写一个boolean[] used来达到同样的目的
3. backtracking只需要一个nums数组作为参数就行

class Solution {  
  
    List<List<Integer>> result = new ArrayList<>();//存储最终结果  
    List<Integer> path = new ArrayList<>();//存储中间结果  
    boolean[] used;//判断哪个数字被使用过  
    public List<List<Integer>> permute(int[] nums) {  
        if (nums.length == 0){  
            return result;  
        }  
        used = new boolean[nums.length];  
        backtracking(nums);  
        return result;  
    }  
  
    private void backtracking(int[] nums){  
        if (path.size() == nums.length){  
            result.add(new ArrayList<>(path));  
            return;  
        }  
        for (int i = 0; i < nums.length; i++){  
            if (used[i]){  
                continue;  
            }  
            used[i] = true;  
            path.add(nums[i]);//加入元素  
            backtracking(nums);//递归  
            path.remove(path.size() - 1);//回溯，删除刚才加入的元素  
            used[i] = false;  
        }  
    }  
}

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入： n = 4, k = 2
输出：
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

示例 2：

输入： n = 1, k = 1
输出：[[1]]

class Solution {
    List<List<Integer>> result = new ArrayList<>();//存储最终结果  
    List<Integer> path = new ArrayList<>();//存储中间结果 
    public List<List<Integer>> combine(int n, int k) {
        backtracing(n,k,1);
        return result;
    }
    private void backtracing(int n,int k,int s){
        if(path.size()==k){
            result.add(new ArrayList<> (path));
            return;
        } 
        for(int i = s;i<=n;i++){
            path.add(i);
            backtracing(n,k,i+1);
            path.remove(path.size() - 1);
        }
    }
}