如何使用C#找到对应于k sum的唯一组合k sum？
创建一个输出列表来存储有效序列，创建一个当前列表来存储在递归树的路径中找到的当前序列。一个回溯函数，将进入递归直到达到目标，否则，当目标小于0时，它应该回溯到前一阶段。在任何时间点，如果目标变为0，则将候选数组添加到结果中候选数组中的值必须与给定的目标相加。
如果不是这些情况，则将候选数组中的元素一一添加并递归前进。
假设数字是5，k是2，所以我们需要形成大小为2的数字组合，形成5。输出将是“1,4”、“2,3”。
示例
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
public class BackTracking{
public void UniqueCombinationSumOfExactKNumbers(int n, int k){
int[] array = new int[n];
for (int i = 1; i < n; i++){
array[i] = i;
}
List currentList = new List();
List> output = new List>();
UniqueCombinationSumOfExactKNumbers(array, n, k, 0, 0, currentList, output);
foreach (var item in output){
StringBuilder s = new StringBuilder();
foreach (var item1 in item){
s.Append(item1.ToString());
}
Console.WriteLine(s);
s = null;
}
}
private void UniqueCombinationSumOfExactKNumbers(int[] array, int target, int countOfNumbers, int sum, int index, List currentList, List> output){
if (sum == target){
if (currentList.Count == countOfNumbers){
List newList = new List();
newList.AddRange(currentList);
output.Add(newList);
return;
}
}
else if (sum > target){
return;
}
else if (currentList.Count == countOfNumbers && sum != target){
return;
}
else{
for (int i = index; i < array.Length; i++){
currentList.Add(array[i]);
UniqueCombinationSumOfExactKNumbers(array, target, countOfNumbers, sum + array[i], i + 1, currentList, output);
currentList.Remove(array[i]);
}
}
}
}
class Program{
static void Main(string[] args){
BackTracking b = new BackTracking();
b.UniqueCombinationSumOfExactKNumbers(5, 2);
}
}
} 输出结果14 23