유효한 시퀀스를 저장할 출력 목록을 만들고, 재귀 트리의 경로에서 찾은 현재 시퀀스를 저장할 현재 목록을 만듭니다. 목표가 달성될 때까지 재귀로 이동하는 역추적 함수, 그렇지 않으면 목표가 0보다 작아질 때 이전 단계로 역추적해야 합니다. 어느 시점에서든 목표가 0이 되면 다음과 같이 결과에 후보 배열을 추가합니다. 후보 배열의 값은 주어진 대상에 합산되어야 합니다.
그렇지 않은 경우 후보 배열에 요소를 하나씩 추가하고 재귀적으로 앞으로 이동합니다.
숫자가 5이고 k가 2이므로 5를 형성하는 크기 2의 숫자 조합을 만들어야 합니다. 출력은 "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