题目链接 代码参考
解题思路： 归并排序+回溯法
提交代码：
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(candidates==null) return result; mergeSort(candidates, 0, candidates.length - 1); findCombination(result,new ArrayList<Integer>(),candidates,target,0); return result; } public void findCombination(List<List<Integer>> result, List<Integer> list,int[] candidates,int target,int pos) { if(target<0) return; else if(target==0) { result.add(new ArrayList<>(list)); return; } else { for(int i=pos;i<candidates.length;i++) { if(candidates[i]>target) break; if(i>pos&&candidates[i]==candidates[i-1]) continue; list.add(candidates[i]); findCombination(result,list,candidates,target-candidates[i],i); list.remove(list.size()-1); } } } public void mergeSort(int[] nums, int left, int right) { if (left >= right) return; int mid = (left + right) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid + 1, right); merge(nums, left, right, mid); } public void merge(int nums[], int left, int right, int mid) { if (left >= right) return; int len = right - left + 1; int[] tmp = new int[len]; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { tmp[k++] = nums[i] < nums[j] ? nums[i++] : nums[j++]; } while (i <= mid) tmp[k++] = nums[i++]; while (j <= right) tmp[k++] = nums[j++]; for (k = 0; k < len; k++) nums[left++] = tmp[k]; } }运行结果：
