因為實驗室項目好久沒刷題了。從今天開始重新開始刷題。

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

感覺一開始審題未認真，以為給的candidates是一個有序數組，按照非降序排列。等到第一次提交了才知道，給的就是一個無序的set。其實也無所謂。寫了個快排，將數組排序。

將每一個元素一次加入到隊列中，只與自己和比自己大的數進行疊加，這樣可以防止重復。當相加和小于target時，將序列加入到隊列中，大于的就不加入，相等的添加結果中。知道隊列為空。

---

public class Solution {
??? public List<List<Integer>> combinationSum(int[] candidates, int target) {
???????
??????? List<List<Integer>> result = new ArrayList<List<Integer>>();
??????? if(candidates.length==0)
??????????? return result;
??????? int start = 0;
??????? int end = candidates.length - 1;
??????? sort(candidates,start,end);
??????? if(candidates[0]>target)
??????????? return result;
???????
??????? while(start<=end&&candidates[start]<=target)
??????? {
??????????? if(candidates[start] == target)
??????????? {
??????????????? List<Integer> tem = new ArrayList<Integer>();
??????????????? tem.add(candidates[start]);
??????????????? result.add(tem);
??????????????? break;
??????????? }
??????????? result.addAll(sum(candidates,target,start,end));
??????????? start++;???????????????????????
??????? }
???????
???????
??????? return result;
???????
??? }
???
??? public List<List<Integer>> sum(int[] candidates,int target,int start,int end)
??? {
??????? List<List<Integer>> result = new ArrayList<List<Integer>>();
??????? LinkedList<Sequence> queue = new LinkedList<Sequence>();
??????? Sequence sequ = new Sequence(candidates[start],start);
??????? queue.add(sequ);
??????? while(!queue.isEmpty())
??????? {
??????????? Sequence element = queue.poll();
??????????? for(int i=element.index;i<=end;i++)
??????????? {
??????????????? if(element.sum + candidates[i]<target)
??????????????? {
??????????????????? Sequence temp = new Sequence();
??????????????????? List<Integer> list = new ArrayList();
??????????????????? list.addAll(element.seq);
??????????????????? list.add(candidates[i]);
??????????????????? temp.set(element.sum + candidates[i], list,i);
??????????????????? queue.addLast(temp);
??????????????? }
??????????????? else if(element.sum + candidates[i]==target)
??????????????? {
??????????????????? List<Integer> list = new ArrayList();
??????????????????? list.addAll(element.seq);
??????????????????? list.add(candidates[i]);
??????????????????? result.add(list);
??????????????? }
??????????????? else
??????????????? {
??????????????????? break;
??????????????? }
??????????? }
??????? }
??????? return result;
??? }
???
??? public int partition(int[] sortArray,int low,int hight)
??? {
?????????? int key = sortArray[low];
????????????

??????????? while(low<hight)

??????????? {

??????????????? while(low<hight && sortArray[hight]>=key)

??????????????????? hight--;

??????????????? sortArray[low] = sortArray[hight];

??????????????? while(low<hight && sortArray[low]<=key)
??????????????????? low++;
??????????????? sortArray[hight] = sortArray[low];
??????????? }
??????????? sortArray[low] = key;
??????????? return low;
??? }

??????? public void sort(int[] sortArray,int low,int hight)

??????? {

??????????? if(low<hight)

??????????? {

??????????????? int result = partition(sortArray,low,hight);

??????????????? sort(sortArray,low,result-1);

??????????????? sort(sortArray,result+1,hight);

??????????? }

??????? }
}

class Sequence
{
??? List<Integer> seq =? new ArrayList();
??? int sum;
??? int index;
??? public Sequence()
??? {
??????? sum = 0;
??? }
??? public Sequence(int num,int index)
??? {
??????? sum = num;
??????? seq.add(num);
??????? this.index = index;
??? }
??? public void set(int sum,List<Integer> list,int index)
??? {
??????? seq = list;
??????? this.sum = sum;
??????? this.index = index;
??? }
???
}

轉載于:https://www.cnblogs.com/jessiading/p/3835333.html

總結

以上是生活随笔為你收集整理的LeetCode Combination Sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。