创建一个输出列表来存储有效序列,创建一个当前列表来存储在递归树的路径中找到的当前序列。一个回溯函数,将进入递归直到达到目标,否则,当目标小于 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<int> currentList = new List<int>(); List<List<int>> output = new List<List<int>>(); 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<int> currentList, List<List<int>> output){ if (sum == target){ if (currentList.Count == countOfNumbers){ List<int> newList = new List<int>(); 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