| 64 | } |
| 65 | |
| 66 | private List<List<Integer>> kSum(int[] nums, int start, int k, int target) { |
| 67 | List<List<Integer>> res = new ArrayList<>(); |
| 68 | if (k == 2) { |
| 69 | int left = start, right = nums.length - 1; |
| 70 | while (left < right) { |
| 71 | int sum = nums[left] + nums[right]; |
| 72 | if (sum == target) { |
| 73 | List<Integer> twoSum = new LinkedList<>(); |
| 74 | twoSum.add(nums[left]); |
| 75 | twoSum.add(nums[right]); |
| 76 | res.add(twoSum); |
| 77 | while (nums[left] == nums[++left] && left < right) ; |
| 78 | while (nums[right] == nums[--right] && left < right) ; |
| 79 | } else if (sum < target) ++left; |
| 80 | else --right; |
| 81 | } |
| 82 | } else { |
| 83 | int i = start, end = nums.length - (k - 1), max = nums[nums.length - 1]; |
| 84 | while (i < end) { |
| 85 | if (nums[i] * k > target) return res; |
| 86 | if (nums[i] + (k - 1) * max < target) { |
| 87 | while (nums[i] == nums[++i] && i < end) ; |
| 88 | continue; |
| 89 | } |
| 90 | List<List<Integer>> temp = kSum(nums, i + 1, k - 1, target - nums[i]); |
| 91 | for (List<Integer> t : temp) { |
| 92 | t.add(0, nums[i]); |
| 93 | } |
| 94 | res.addAll(temp); |
| 95 | while (nums[i] == nums[++i] && i < end) ; |
| 96 | } |
| 97 | } |
| 98 | return res; |
| 99 | } |
| 100 | |
| 101 | public static void main(String[] args) { |
| 102 | Solution solution = new Solution(); |