LeetCode： 18. 四数之和
递归回溯， 只[去重]必然超时
重点剪枝
先对 数组 nums 排序(从小到大) >> 方便剪枝
当接下的可选择的元素不够 list 添加到 4 位时，可提前退出了在递归的同一层中，第二轮开始，当前的元素与前一个相同，跳过。>> 去重 在这一步实现当前数 + 已累加的和 + 下一个元素 * list 剩余还能加入数的个数 ，如果大于target，所以往后的再加都会继续大于， 可以直接退出了当前数 + 已累加的和 + 数组中最后一个元素 * list 剩余的还能加入数的个数， 如果小于target，所以当前数不够大，往后加都会小于target，跳过当前数，进行下一次循环 class Solution { List<List<Integer>> ans = new ArrayList<>(); List<Integer> list = new ArrayList<>(); int[] arr ; int sum; int size; int tar ; public List<List<Integer>> fourSum(int[] nums, int target) { if (nums == null || nums.length == 0) return ans; size = nums.length; if(size < 4) return ans; arr = nums; tar = target; // 排好序 Arrays.sort(arr); dfs(0, 0); return ans; } public void dfs(int start, int sum) { if (sum == tar && list.size() == 4) { ans.add(new ArrayList<>(list)); return; } for (int i = start ; i < size; i++) { // 剪枝 // 剩下的不够组成 4 个 数了 if(size - i < (4 - list.size())) return ; // 去重 // 在同一层递归中，第二轮开始，当前的元素 == 前一个元素 if(i > start && arr[i] == arr[i - 1]) continue ; // 剪枝 // 如果当前数 + 已加/减的数 + 下一个元素 * 还能加入数的个数 > 大于 target if(i < size - 1 && (arr[i] + sum + arr[i + 1] * (4 - 1 - list.size())) > tar ) return ; // 剪枝 // 如果当前数 + 已加/减的数 + 数组中最后一个元素 * 还能加入数的个数 < target if(i < size - 1 && (arr[i] + sum + arr[size - 1] * (4 - 1 - list.size())) < tar) continue ; // dfs list.add(arr[i]); dfs(i + 1, sum + arr[i]); list.remove(list.size() - 1); } } }>> 题解
