回溯的本质就是做选择，形成一个选择的递归树，每一个分支都是一个方案。形成了一个多叉树，每一条路径就是做一个选择，就是多叉树的前序遍历，当到达一个叶节点的时候，就是一个方案，到达叶节点时候，设置的存储状态的数，或者数组，或者状态boolean值，对这个进行逻辑判断，来查看是否是一个方案。
回溯就发生在后序的位置，回溯刚才做的选择。

一般查看是否能够成功形成一种方案满足条件时候，为了节约大量计算，只要有一个到达叶节点的方案可以满足，那么就直接return true。

另外，这种数划分成集合，就想象成高中课讲的排列组合，小球装到盒子里，回溯DFS做的就是遍历每一个小球，枚举小球能放到各个盒子里的情况，递归下一层的时候，就是放入下一个小球的选择。
698. Partition to K Equal Sum Subsets

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if(k > nums.length) return false;
        int sum = 0;
        for(int i : nums) sum += i;
        if(sum % k != 0) return false;

        int target = sum / k;
        int[] bucket = new int[k];
        return dfs(nums, 0, bucket, target);
    }

    public boolean dfs(int[] nums, int index, int[] bucket, int target){
        if(index == nums.length){
            for(int i = 0; i < bucket.length; i++){
                if(bucket[i] != target) return false;
            }
            return true;
        }

        for(int i = 0; i < bucket.length; i++){
            if(bucket[i] + nums[index] > target) continue;
            bucket[i] += nums[index];
            //这个就是当有一个方案，如果他可以，那么就直接return true，节省大量计算
            if(dfs(nums, index + 1, bucket, target)) return true; 
            bucket[i] -= nums[index];
        }
        return false;
    }  
}

对于一个原有集合做排列，组合，或者找子集，无外乎就是三种形式，
1.没有重复元素元素不能被重复使用
2.有重复元素，但是不能被重复使用
3.可以被重复使用(可以被重复使用，就相当于有重复了)
没有重复的数组
子集问题
子集问题，画出递归树，每做一次选择都是一个子集，找子集，要避免找到重复方案，什么是重复方案，比如[1, 2, 3]， 对于[1, 2]和[2, 1]其实是一种方案，那么就要避免找到重复的方案，如何避免找到重复方案，使用指针，只往这个指针的后面去找新加入的数，不能往前走，这样就避免了重复情况的发生。下一层可以选择的，就在这个指针后面找。

组合问题，其实也是找子集的问题，找到指定个数的数的集合，就是找那个个数的子集。那么就在子集问题上加一个条件，当path数组长度是想要的长度时，就直接加入到最终答案当中。

排列问题需要加入visit数组判断是否走过的原因是，index指针没有用，排列问题，可以往前找之前的数字，因为排列问题顺序的不同，是不同的排列，是不同的结果。

对于可能存在重复元素的数组
画出递归树，会发现，需要剪枝的就是重复的，这种重复是什么重复呢，就是如果数组排成有序的，当做选择时，如果这个数和前一个数相等，那么其实这个数的选择已经做过了，可以跳过去
对于有重复的组合/子集问题，让原数组有序，在同一层做选择的时候，如果是和前一个数一样，那么就不用选择了，直接跳过就好了。

对于排列问题，如果原数组有重复的话，首先要排序，比如连续的4，4，4，4。不同个数的4才能组成不同的排列，，其余，如果只选择一个，不论选哪个4，他都是4，选择两个4的时候，所以对于相同的一列数，组排列，只有前面的数用过了，他才可以用，如果前面的数没用过，选择方案，也肯定是选择他前面的数，如果第一个4没被用过，只选一个4，无论如何也不能用第二个4，这也是对于相同的数，排列组合的一种剪枝方法

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    // 如果前面的相邻相等元素没有用过，则跳过
    continue;
}

数组中，元素可以重复选择
如何处理元素可以重复使用这个逻辑，不能重复使用的时候，我们是设置一个index，下一次从index+1开始递归，那么怎么样能够让这个元素可以重复使用，又不会往回找，那么就是下一次递归从index开始递归，这样就解决了可以重复使用的问题。如果这个index可以从头开始来，那么就相当于下一次的index可以往前找了。就会有重复方案了
例如[1,2,3] 如果递归到2了，下一次从index + 1 也就是3进行下一次递归，这样就是没有重复，就相当于没有重复找子集， 如果下一次递归可以从index 1走，那么就是2可以重复， 如果下一次的index没有限制，那么就相当于可以从头走了

排列问题，一般情况都要有一个visit数组用来剪枝，因为排列问题每次都要从数组头开始寻找,所以用这个visit数组进行剪枝，而_组合/子集_问题 其实本质是一类问题，找组合问题就是要避免往回找，找到重复的，所以要有一个index，指引你递归时候从哪开始找。而这里又涉及到两种题型，一种是 元素可以重复使用，一种是元素不可以重复使用，对于不可以重复使用的，递归的下一层要从i + 1开始枚举，而可以重复使用的就是继续从i开始搜索就行了(无论那种，因为又index索引的存在，都使得下一层的递归不会往回搜索)

对于排列问题和组合问题，在有重复元素下的剪枝方式不同
排列

 if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }

组合问题

 if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }