public class Solution
{
List<IList<int>> list = new List<IList<int>>();//全部记录
List<int> records = new List<int>();//一条记录
bool bk = false;
private void BackTrack(List<int> candidates, int target, int sum)
{
if (sum == target)
{
int[] temp = new int[records.Count];
records.CopyTo(temp);
bool same = false;
foreach (var l in list)
{
if (l.Count == temp.Length)
{
var l1 = l.OrderBy(x => x).ToList();
var l2 = temp.OrderBy(x => x).ToList();
var samecount = ;
for (int x = ; x < l1.Count; x++)
{
if (l1[x] == l2[x])
{
samecount++;
}
}
if (samecount == l.Count)
{
same = true;
break;
}
}
}
if (!same)
{
list.Add(temp.ToList());
}
bk = true;
return;
}
else if (sum < target)
{
bk = true;
for (int position = ; position < candidates.Count; position++)
{
var cur = candidates[position];
sum += cur;
records.Add(cur);
BackTrack(candidates, target, sum);
//回溯
records.RemoveAt(records.Count - );
sum -= cur;
if (bk)
{
bk = false;
break;
}
}
}
else
{
bk = true;
return;
}
} public IList<IList<int>> CombinationSum(int[] candidates, int target)
{
var can = candidates.OrderBy(x => x).ToList();
BackTrack(can, target, );
return list;
}
}
补充一个python的实现，写的要简单的多了：
class Solution:
def dfs(self,candidates,target,index,path,l):
if target < 0:
return
elif target == 0:
l.append(path)
return
for i in range(index,len(candidates)):
self.dfs(candidates,target-candidates[i],i,path+[candidates[i]],l)
return def combinationSum(self, candidates: 'List[int]', target: 'int') -> 'List[List[int]]':
l = list()
path = []
candidates.sort()
self.dfs(candidates,target,0,path,l)
return l