由三数之和 到 多数之和———解析回溯算法的思想

首先来看三数之和

题目描述：给你一个整数数组 nums和整数值target ，在该数组中寻找三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == target 。请你返回一个和为 target 且不重复的三元组,返回值为int[]类型。

题目分析：该题是力扣经典例题：两数之和的变式，分析方法同理，只不过需要多嵌套一层循环。

先来分析两数之和的大概思路，

方法一：双层for循环，定一寻一暴力法，不再赘叙。 方法二：定一寻一暴力法的改版，只不过利用了Java的Hashmap，优化了时间复杂度到,假设A+B=target目标值，简单总结就是三个词：定A，查B，putA，这其中查B需要使用到HashMap中的containsKey(key)方法，查找是否存在该key，返回值为boolean类型。查不到该key则将A放入map集合中，查得到则返回A对应的数组下标和key对应的value，这里值得注意的是，由于containsKey方法是根据键查找值，而题目要求我们返回的数组下标，所以这里我们将数组元素存放到map集合时，应当把数组值当作key，将数组下标当作value，这样才能判断是否找到我们想要的数组值。

接下来来看看两数之和的代码实现

public int[] findTwoByMap(int[] nums, int target) {
        //方法二，哈希映射法
        Map<Integer,Integer> map = new HashMap<>();
        for(int i= 0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("不存在这样的两个数");
    }

同理我们再来分析三数之和

在两数之和中，我们分析了主要思路，定一寻一的方法，同理在三数之和中采用了定一，再定一，再寻一的方法，层层套娃，多加了个for循环罢了，不再赘叙。

三数之和代码实现：

public static void main(String[] args) {
    int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int target = 13;
    int[] ints = findThreeByMap(nums, target);
    for (int i:
         ints) {
        System.out.println(i);//组成方式不唯一，第一个找到的是1，9，0，
    }

}
public static int[] findThreeByMap(int[] nums, int target) {
    // 测试三数字之和
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            int complement = target - nums[i] - nums[j];
            if (map.containsKey(complement) && map.get(complement) != i && map.get(complement) != j) {
                return new int[]{i, j, map.get(complement)};
            }
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("不存在这样的三个数");
}

但是需要注意的是，多解的情况下该方法无法找到数组中所有的搭配类型，只能找到第一个符合描述的三个数组元素，如果想要找到所有符合描述的三个元素，只需要在如上代码第18行中修改成能够存储二维数组的语句，将异常处理语句改为return 这个二维数组的语句即可，同时方法的返回值类型也需要更改。

三数之和代码最终实现：

public static ArrayList<int[]> test5(int[] nums, int target) {
    // 测试三数字之和
    HashMap<Integer, Integer> map = new HashMap<>();
    //定列数不定行数的额二维数组
    //int[][] intsResult = new int[10][3];
    ArrayList<int[]> intsResult = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            int complement = target - nums[i] - nums[j];
            if (map.containsKey(complement) && map.get(complement) != i && map.get(complement) != j) {
                int[] ints = new int[3];
                ints[0] = i;
                ints[1] = j;
                ints[2] = map.get(complement);
                intsResult.add(ints);
            }
        }
        map.put(nums[i], i);
    }
    return intsResult;
}
public static void main(String[] args) {
    int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    //  数组位置  0  1  2  3  4  5  6  7  8   9
    int target = 13;
    ArrayList<int[]> intResult = test5(nums, target);
    for (int[] array : intResult) {
        for (int num : array) {
            System.out.print(num + " ");
        }
        System.out.println(); // 换行
    }


}

测试样例

测试结果

即然有了两数之和、三数之和，要不要试着推广到多数之和呢，em....感觉好像就层层套娃，不，其实没那么简单,这里我们便引入到一个解决类似多数之和排列组合问题的常用解决方案：回溯算法。

什么是回溯算法，归根结底,其实就是一种纯暴力方法，虽然它暴力但是在解决一些排列组合问题的情况下，我们必须要求出所有的解，这个时候回溯法便可以通过递归回溯调用找到所有的解。 我们来看代码实现

回溯的backtracking方法

private static void backtracking(int[] nums, int target, int start, List<Integer> current, List<List<Integer>> result) {
    //回溯终止条件 当target减到0时，表示找到了一个符合的解
    if (target == 0) {
        result.add(new ArrayList<>(current));//添加符合条件的元素下标数组
        return;//回溯退出条件
    }
    for (int i = start; i < nums.length; i++) {

        if (nums[i] <= target) {//只有当该元素的值小于目标值时才有可能找到对应组合，元素值大于target则直接跳过
            //处理节点
            current.add(i);//添加元素
            //递归
            backtracking(nums, target - nums[i], i + 1, current, result); // 注意这里是 i + 1
            //回溯：撤销处理节点的情况
            //即：找到一个解后，在回溯算法中 需要将最后一个元素去除，以便判断这最后一个元素是否还有后序的元素代替
            current.remove(current.size() - 1);//移除最后一个元素
        }
    }
}

回溯算法的重点是回溯操作， 总的来说就是current.remove(current.size() - 1);//移除最后一个元素回到上一层这一行代码，搞清楚这行代码与for循环中遍历元素的关系，回溯的大概流程就清楚了。 当在某一次递归调用过程中，3+10=13，得到了我们想要的target13，此时应当想到，最后一个元素6是内层一次递归时得到的解，此时可以判断，与3搭配的解后续是否还存在呢，3是否可以和后序的元素7，8，9....多个数元素继续组合得到target13呢（例如3+6+4=target13），于是，当这次递归时，我们得到这个满足的组合，不仅需要，先将这个解存储起来，还要后remove掉最后一个元素10，再次回到上一次递归调用过程3中，再次判断后序是否有其他组合3+...+....+..=13成立,这里的回，便是回溯算法中最重要的一环，只有回溯寻找所有情况的排列组合，才可以判断出所有可能。

这次成功，remove(10) ，包含3的基础上继续递归+for循环寻找其他解

初始数组

这次成功

下次成功

多数之和测试（数组元素不重复的情况下）

测试用例

测试代码

@Test
public void test6(){
    int[] nums = {1, 3, 2, 10, 7, 6, 8, 9, 5, 4};
    //  数组位置   0, 1, 2,  3, 4, 5, 6, 7, 8, 9
    int target = 13;
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> current = new ArrayList<>();
    backtracking(nums, target, 0, current, result);
    for (List<Integer> list : result) {
        System.out.println(list);
    }
}

测试结果 （数值表示元素下标）

总结

回溯算法的应用并不仅仅包括排列组合，还在图的着色问题、排列问题、字符串匹配等方面也有广泛应用，本文所给的的回溯算法仅仅是最基础的方案，还有许多优化的空间，通过更换效率更高的的数据结构、剪枝优化（通过增加其他判断提前退出不必要的递归）、记忆化搜索等等，感兴趣的也可以去搜索经典的八皇后问题，这里不再赘叙。