유효한 시퀀스를 저장할 출력 목록을 만들고, 재귀 트리의 경로에서 찾은 현재 시퀀스를 저장할 현재 목록을 만듭니다. 목표가 달성될 때까지 재귀로 이동하는 역추적 함수, 그렇지 않으면 목표가 0보다 작아질 때 이전 단계로 역추적해야 합니다. 어느 시점에서든 목표가 0이 되면 다음과 같이 결과에 후보 배열을 추가합니다. 후보 배열의 값은 주어진 대상에 합산되어야 합니다.
그렇지 않은 경우 후보 배열에 요소를 하나씩 추가하고 재귀적으로 앞으로 이동합니다.
예를 들어 숫자가 5이므로 5를 구성하는 숫자를 찾아야 합니다. 출력은 "1,4","2,3",5가 됩니다. 출력에서 014,.023 및 05를 삭제할 수 있습니다.
예
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
public class BackTracking{
public void UniqueCombinationOfNumbersCorrespondsToSum(int n){
int[] array = new int[n + 1];
for (int i = 1; i <= n; i++){
array[i] = i;}
List<int> currentList = new List<int>();
List<List<int>> output = new List<List<int>>();
UniqueCombinationSum(array, n, 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 UniqueCombinationSum(int[] array, int target, int sum, int index, List<int> currentList, List<List<int>> output){
if (sum == target){
List<int> newList = new List<int>();
newList.AddRange(currentList);
output.Add(newList);
return;
}
else if (sum > target){
return;
}
else{
for (int i = index; i < array.Length; i++){
currentList.Add(array[i]);
UniqueCombinationSum(array, target, sum + array[i], i + 1, currentList, output);
currentList.Remove(array[i]);
}
}
}
}
class Program{
static void Main(string[] args){
BackTracking b = new BackTracking();
b.UniqueCombinationOfNumbersCorrespondsToSum(5);
}
}
}
} 출력
14 23 05