List<int> myList = new List<int>() {5,7,12,8,7};
我也有一个目标：
int target = 20;
20，我需要这样一个列表：{ 12, 8 }
{ 7, 12, 7 }
每个数字只能使用一次（7出现两次因为它在列表中出现了两次）。如果没有解决方案，则应返回一个空列表。有人知道我如何做到这样吗？
这是一个统计学问题。您想要找到所有可能的组合，并且它们的和相匹配。我可以推荐这个项目，也值得一读：
http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G
然后，这变得容易且高效：
List<int> myList = new List<int>() { 5, 7, 12, 8, 7 };
var allMatchingCombos = new List<IList<int>>();
for (int lowerIndex = 1; lowerIndex < myList.Count; lowerIndex++)
{
IEnumerable<IList<int>> matchingCombos = new Combinations<int>(myList, lowerIndex, GenerateOption.WithoutRepetition)
.Where(c => c.Sum() == 20);
allMatchingCombos.AddRange(matchingCombos);
}
foreach(var matchingCombo in allMatchingCombos)
Console.WriteLine(string.Join(",", matchingCombo));
输出：
12,8
5,7,8
5,8,7
Variations。 - Tim Schmelterstatic void Main(string[] args)
{
const int target = 20;
var numbers = new List<int> { 1, 2, 5, 8, 12, 14, 9 };
Console.WriteLine($"Number of Combinations: {SumCounter(numbers, target)}");
Console.ReadKey();
}
private static int SumCounter(IReadOnlyList<int> numbers, int target)
{
var result = 0;
RecursiveCounter(numbers, target, new List<int>(), ref result);
return result;
}
private static void RecursiveCounter(IReadOnlyList<int> numbers, int target, List<int> partial, ref int result)
{
var sum = partial.Sum();
if (sum == target)
{
result++;
Console.WriteLine(string.Join(" + ", partial.ToArray()) + " = " + target);
}
if (sum >= target) return;
for (var i = 0; i < numbers.Count; i++)
{
var remaining = new List<int>();
for (var j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);
var partRec = new List<int>(partial) { numbers[i] };
RecursiveCounter(remaining, target, partRec, ref result);
}
}
2. 使用 Linq 获取子集
static void Main(string[] args)
{
const int target = 20;
var numbers = new int[] { 1, 2, 5, 8, 12, 14, 9 };
var matches = numbers.GetSubsets().Where(s => s.Sum() == target).ToArray();
foreach (var match in matches) Console.WriteLine(match.Select(m => m.ToString()).Aggregate((a, n) => $"{a} + {n}") + $" = {target}");
Console.WriteLine($"Number of Combinations: {matches.Length}");
Console.ReadKey();
}
}
public static class Extension
{
public static IEnumerable<IEnumerable<T>> GetSubsets<T>(this IEnumerable<T> collection)
{
if (!collection.Any()) return Enumerable.Repeat(Enumerable.Empty<T>(), 1);
var element = collection.Take(1);
var ignoreFirstSubsets = GetSubsets(collection.Skip(1));
var subsets = ignoreFirstSubsets.Select(set => element.Concat(set));
return subsets.Concat(ignoreFirstSubsets);
}
3. 另一种递归方法...
static void Main(string[] args)
{
const int target = 20;
var numbers = new [] { 1, 2, 5, 8, 12, 14, 9 };
var result = GetSubsets(numbers, target, "");
foreach (var subset in result) Console.WriteLine($"{subset} = {target}");
Console.WriteLine($"Number of Combinations: {result.Count()}");
Console.ReadLine();
}
public static IEnumerable<string> GetSubsets(int[] set, int sum, string values)
{
for (var i = 0; i < set.Length; i++)
{
var left = sum - set[i];
var vals = values != "" ? $"{set[i]} + {values}" : $"{set[i]}";
if (left == 0) yield return vals;
else
{
int[] possible = set.Take(i).Where(n => n <= sum).ToArray();
if (possible.Length <= 0) continue;
foreach (string s in GetSubsets(possible, left, vals)) yield return s;
}
}
}
4. 使用二分查找。线性时间。
static void Main(string[] args)
{
const int target = 20;
var numbers = new [] { 1, 2, 5, 8, 12, 14, 9 };
var subsets = GetSubsets(numbers, target);
foreach (var s in subsets) Console.WriteLine($"{s} = {target}");
Console.WriteLine($"Number of Combinations: {subsets.Count()}");
Console.ReadKey();
}
private static IEnumerable<string> GetSubsets(int[] array, int target)
{
Array.Sort((Array)array);
List<string> result = new List<string>();
for (int i = array.Length-1; i >= 0; i--)
{
var eq = $"{array[i]}";
var sum = array[i];
var toAdd = 0;
while (sum != target)
{
var mid = Array.BinarySearch(array, 0, sum <= target / 2 && sum != array[i] ? array.Length - 1 : i, target - sum);
mid = mid < 0 ? ~mid - 1 : mid;
if (mid == i || mid < 0 || toAdd == array[mid] ) break;
toAdd = array[mid];
sum += array[mid];
eq += $" + {array[mid]}";
if (sum == target) result.Add(eq);
}
}
return result;
}
使用递归。请注意，此解决方案将倾向于使用列表中的前几个项目获得的解决方案。因此，对于目标为20的情况，您将不会得到12+8作为解决方案，而是5+7+8。
List<int> findSum(List<int> numbers, int target, int index = 0)
{
// loop through all numbers starting from the index
for (var i = index; i < numbers.Count; i++)
{
int remainder = target - numbers[i];
// if the current number is too big for the target, skip
if (remainder < 0)
continue;
// if the current number is a solution, return a list with it
else if (remainder == 0)
return new List<int>() { numbers[i] };
else
{
// otherwise try to find a sum for the remainder later in the list
var s = findSum(numbers, remainder, i + 1);
// if no number was returned, we could’t find a solution, so skip
if (s.Count == 0)
continue;
// otherwise we found a solution, so add our current number to it
// and return the result
s.Insert(0, numbers[i]);
return s;
}
}
// if we end up here, we checked all the numbers in the list and
// found no solution
return new List<int>();
}
void Main()
{
List<int> myList = new List<int>() { 5, 7, 12, 8, 7 };
Console.WriteLine(findSum(myList, 12)); // 5, 7
Console.WriteLine(findSum(myList, 20)); // 5, 7, 8
Console.WriteLine(findSum(myList, 31)); // 5, 7, 12, 7
}
if 和 else if 结合起来，以在 remainder 低于或等于零时立即返回解决方案。 - poke我在C#中的这个实现将返回所有等于给定数字的组合（包括重复使用相同数字）。
string r;
List<int> l = new List<int>();
void u(int w, int s, int K, int[] A) {
// If a unique combination is found
if (s == K) {
r += "(" + String.Join(" ", l) + ")";
return;
}
// For all other combinations
for (int i=w; i<A.Length; i++){
// Check if the sum exceeds K
int x = A[i];
if (s + x <= K){
l.Add(x);
u(i, s + x, K,A);
l.Remove(x);
}
}
}
string combinationSum(int[] a, int s) {
r = "";
u(0, 0, s, a.Distinct().OrderBy(x=>x).ToArray());
return r.Any() ? r : "Empty";
}
对于a: [2, 3, 5, 9] 和 s = 9
结果为： “(2 2 2 3)(2 2 5)(3 3 3)(9)”
List<int>数组？ - Icemanind