# Q：发现与重复无序的正整数n个大小的一个包和所有的k-子集

Please note that this is required for a C# .NET 2.0 project (Linq not allowed).

I know very similar questions have been asked here and I have already produce some working code (see below) but still would like an advice as to how to make the algorithm faster given k and s conditions.

This is what I've learnt so far: Dynamic programming is the most efficient way to finding ONE (not all) subsets. Please correct me if I am wrong. And is there a way of repeatedly calling the DP code to produce newer subsets till the bag (set with duplicates) is exhausted?

If not, then is there a way that may speed up the backtracking recursive algorithm I have below which does produce what I need but runs in O(2^n), I think, by taking s and k into account?

Here is my fixed bag of numbers that will NEVER change with n=114 and number range from 3 to 286:

``````    int[] numbers = new int[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
};
``````

Requirements

• Space limit to 2-3GB max but time should be O(n^something) not (something^n).

• The bag must not be sorted and duplicate must not be removed.

• The result should be the indices of the numbers in the matching subset, not the numbers themselves (as we have duplicates).

Dynamic Programming Attempt

Here is the C# dynamic programming version adapted from an answer to a similar question here on stackoverflow.com:

``````using System;
using System.Collections.Generic;

namespace Utilities
{
public static class Combinations
{
private static Dictionary<int, bool> m_memo = new Dictionary<int, bool>();
private static Dictionary<int, KeyValuePair<int, int>> m_previous = new Dictionary<int, KeyValuePair<int, int>>();
static Combinations()
{
m_memo.Clear();
m_previous.Clear();
m_memo[0] = true;
m_previous[0] = new KeyValuePair<int, int>(-1, 0);

}

public static bool FindSubset(IList<int> set, int sum)
{
//m_memo.Clear();
//m_previous.Clear();
//m_memo[0] = true;
//m_previous[0] = new KeyValuePair<int, int>(-1, 0);

for (int i = 0; i < set.Count; ++i)
{
int num = set[i];
for (int s = sum; s >= num; --s)
{
if (m_memo.ContainsKey(s - num) && m_memo[s - num] == true)
{
m_memo[s] = true;

if (!m_previous.ContainsKey(s))
{
m_previous[s] = new KeyValuePair<int, int>(i, num);
}
}
}
}

return m_memo.ContainsKey(sum) && m_memo[sum];
}
public static IEnumerable<int> GetLastIndex(int sum)
{
while (m_previous[sum].Key != -1)
{
yield return m_previous[sum].Key;
sum -= m_previous[sum].Value;
}
}

public static void SubsetSumMain(string[] args)
{
int[] numbers = new int[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
};

int sum = 400;
//int size = 4; // don't know to use in dynamic programming

// call dynamic programming
if (Numbers.FindSubset(numbers, sum))
{
foreach (int index in Numbers.GetLastIndex(sum))
{
Console.Write((index + 1) + "." + numbers[index] + "\t");
}
Console.WriteLine();
}
Console.WriteLine();

}
}
}
``````

Recursive Programming Attempt

and Here is the C# recursive programming version adapted from an answer to a similar question here on stackoverflow.com:

``````using System;
using System.Collections.Generic;

namespace Utilities
{
public static class Combinations
{
private static int s_count = 0;
public static int CountSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
{
if ((numbers.Length <= index) || (current > sum)) return 0;
if (result == null) result = new List<int>();

List<int> temp = new List<int>(result);
if (current + numbers[index] == sum)
{
if ((size == 0) || (temp.Count == size))
{
s_count++;
}
}
else if (current + numbers[index] < sum)
{
CountSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
}

CountSubsets(numbers, index + 1, current, sum, size, result);
return s_count;
}

private static List<List<int>> m_subsets = new List<List<int>>();
public static List<List<int>> FindSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
{
if ((numbers.Length <= index) || (current > sum)) return m_subsets;
if (result == null) result = new List<int>();

List<int> temp = new List<int>(result);
if (current + numbers[index] == sum)
{
if ((size == 0) || (temp.Count == size))
{
}
}
else if (current + numbers[index] < sum)
{
FindSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
}

FindSubsets(numbers, index + 1, current, sum, size, result);

return m_subsets;
}

public static void SubsetSumMain(string[] args)
{
int[] numbers = new int[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
};

int sum = 17;
int size = 2;

// call backtracking recursive programming
Console.WriteLine("CountSubsets");
int count = Numbers.CountSubsets(numbers, 0, 0, sum, size, null);
Console.WriteLine("Count = " + count);
Console.WriteLine();

// call backtracking recursive programming
Console.WriteLine("FindSubsets");
List<List<int>> subsets = Numbers.FindSubsets(numbers, 0, 0, sum, size, null);
for (int i = 0; i < subsets.Count; i++)
{
if (subsets[i] != null)
{
Console.Write((i + 1).ToString() + ":\t");
for (int j = 0; j < subsets[i].Count; j++)
{
int index = subsets[i][j];
Console.Write((index + 1) + "." + numbers[index] + " ");
}
Console.WriteLine();
}
}
Console.WriteLine("Count = " + subsets.Count);

}
}
}
``````

Please let me know how to restrict the dynamic programming version to subsets of size k and if I can call it repeatedly so it returns different subsets on every call until there are no more matching subsets.

Also I am not sure where to initialize the memo of the DP algorithm. I did it in the static constructor which auto-runs when accessing any method. Is this the correct initialization place or does it need to be moved to inside the FindSunset() method [commented out]?

As for the recursive version, is it backtracking? and how can we speed it up. It works correctly and takes k and s into account but totally inefficient.

Let's make this thread the mother of all C# SubsetSum related questions!

This is what I've learnt so far: Dynamic programming is the most efficient way to finding ONE (not all) subsets. Please correct me if I am wrong. And is there a way of repeatedly calling the DP code to produce newer subsets till the bag (set with duplicates) is exhausted?

``````    int[] numbers = new int[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
};
``````

• Space limit to 2-3GB max but time should be O(n^something) not (something^n).

• 不能将袋子分类和复制，不能移除。

• The result should be the indices of the numbers in the matching subset, not the numbers themselves (as we have duplicates).

``````using System;
using System.Collections.Generic;

namespace Utilities
{
public static class Combinations
{
private static Dictionary<int, bool> m_memo = new Dictionary<int, bool>();
private static Dictionary<int, KeyValuePair<int, int>> m_previous = new Dictionary<int, KeyValuePair<int, int>>();
static Combinations()
{
m_memo.Clear();
m_previous.Clear();
m_memo[0] = true;
m_previous[0] = new KeyValuePair<int, int>(-1, 0);

}

public static bool FindSubset(IList<int> set, int sum)
{
//m_memo.Clear();
//m_previous.Clear();
//m_memo[0] = true;
//m_previous[0] = new KeyValuePair<int, int>(-1, 0);

for (int i = 0; i < set.Count; ++i)
{
int num = set[i];
for (int s = sum; s >= num; --s)
{
if (m_memo.ContainsKey(s - num) && m_memo[s - num] == true)
{
m_memo[s] = true;

if (!m_previous.ContainsKey(s))
{
m_previous[s] = new KeyValuePair<int, int>(i, num);
}
}
}
}

return m_memo.ContainsKey(sum) && m_memo[sum];
}
public static IEnumerable<int> GetLastIndex(int sum)
{
while (m_previous[sum].Key != -1)
{
yield return m_previous[sum].Key;
sum -= m_previous[sum].Value;
}
}

public static void SubsetSumMain(string[] args)
{
int[] numbers = new int[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
};

int sum = 400;
//int size = 4; // don't know to use in dynamic programming

// call dynamic programming
if (Numbers.FindSubset(numbers, sum))
{
foreach (int index in Numbers.GetLastIndex(sum))
{
Console.Write((index + 1) + "." + numbers[index] + "\t");
}
Console.WriteLine();
}
Console.WriteLine();

}
}
}
``````

``````using System;
using System.Collections.Generic;

namespace Utilities
{
public static class Combinations
{
private static int s_count = 0;
public static int CountSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
{
if ((numbers.Length <= index) || (current > sum)) return 0;
if (result == null) result = new List<int>();

List<int> temp = new List<int>(result);
if (current + numbers[index] == sum)
{
if ((size == 0) || (temp.Count == size))
{
s_count++;
}
}
else if (current + numbers[index] < sum)
{
CountSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
}

CountSubsets(numbers, index + 1, current, sum, size, result);
return s_count;
}

private static List<List<int>> m_subsets = new List<List<int>>();
public static List<List<int>> FindSubsets(int[] numbers, int index, int current, int sum, int size, List<int> result)
{
if ((numbers.Length <= index) || (current > sum)) return m_subsets;
if (result == null) result = new List<int>();

List<int> temp = new List<int>(result);
if (current + numbers[index] == sum)
{
if ((size == 0) || (temp.Count == size))
{
}
}
else if (current + numbers[index] < sum)
{
FindSubsets(numbers, index + 1, current + numbers[index], sum, size, temp);
}

FindSubsets(numbers, index + 1, current, sum, size, result);

return m_subsets;
}

public static void SubsetSumMain(string[] args)
{
int[] numbers = new int[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
};

int sum = 17;
int size = 2;

// call backtracking recursive programming
Console.WriteLine("CountSubsets");
int count = Numbers.CountSubsets(numbers, 0, 0, sum, size, null);
Console.WriteLine("Count = " + count);
Console.WriteLine();

// call backtracking recursive programming
Console.WriteLine("FindSubsets");
List<List<int>> subsets = Numbers.FindSubsets(numbers, 0, 0, sum, size, null);
for (int i = 0; i < subsets.Count; i++)
{
if (subsets[i] != null)
{
Console.Write((i + 1).ToString() + ":\t");
for (int j = 0; j < subsets[i].Count; j++)
{
int index = subsets[i][j];
Console.Write((index + 1) + "." + numbers[index] + " ");
}
Console.WriteLine();
}
}
Console.WriteLine("Count = " + subsets.Count);

}
}
}
``````

My previous answer works on the principle of cutting off the number of combinations to check. But this can be improved significantly once you sort the array. The principle is similar, but since the solution is entirely different, I've decided to put it in a separate answer.

I was careful to use only .Net Framework 2.0 features. Might add a visual explanation later, but the comments should be enough.

``````class Puzzle
{

public Puzzle(int[] numbers)
{
// Set N and make Elements array
// (to remember the original index of each element)
this.N = numbers.Length;
this.Elements = new SubsetElement[this.N];

for (var i = 0; i < this.N; i++)
{
this.Elements[i] = new SubsetElement(numbers[i], i);
}

// Sort Elements descendingly by their Number value
Array.Sort(this.Elements, (a, b) => b.Number.CompareTo(a.Number));

// Save tail-sums to allow immediate access by index
// Allow immedate calculation by index = N, to sum 0
this._tailSums = new int[this.N + 1];
var sum = 0;

for (var i = this.N - 1; i >= 0; i--)
{
this._tailSums[i] = sum += this.Elements[i].Number;
}
}

public void Solve(int s, Action<SubsetElement[]> callback)
{
for (var k = 1; k <= this.N; k++)
this.Solve(k, s, callback);
}

public void Solve(int k, int s, Action<SubsetElement[]> callback)
{
this.ScanSubsets(0, k, s, new List<SubsetElement>(), callback);
}

private void ScanSubsets(int startIndex, int k, int s,
List<SubsetElement> subset, Action<SubsetElement[]> cb)
{
// No more numbers to add, and current subset is guranteed to be valid
if (k == 0)
{
// Callback with current subset
cb(subset.ToArray());
return;
}

// Sum the smallest k elements
var minSubsetStartIndex = this.N - k;
var minSum = this._tailSums[minSubssetStartIndex];

// Smallest possible sum is greater than wanted sum,
// so a valid subset cannot be found
if (minSum > s)
{
return;
}

// Find largest number that satisfies the condition
// that a valid subset can be found
minSum -= this.Elements[minSubsetStartIndex].Number;

// But remember the last index that satisfies the condition
var minSubsetEndIndex = minSubsetStartIndex;

while (minSubsetStartIndex > startIndex &&
minSum + this.Elements[minSubsetStartIndex - 1].Number <= s)
{
minSubsetStartIndex--;
}

// Find the first number in the sorted sequence that is
// the largest number we just found (in case of duplicates)
while (minSubsetStartIndex > startIndex &&
Elements[minSubsetStartIndex] == Elements[minSubsetStartIndex - 1])
{
minSubsetStartIndex--;
}

// [minSubsetStartIndex .. maxSubsetEndIndex] is the
// full range we must check in recursion

for (var subsetStartIndex = minSubsetStartIndex;
subsetStartIndex <= minSubsetEndIndex;
subsetStartIndex++)
{
// Find the largest possible sum, which is the sum of the
// k first elements, starting at current subsetStartIndex
var maxSum = this._tailSums[subsetStartIndex] -
this._tailSums[subsetStartIndex + k];

// The largest possible sum is less than the wanted sum,
// so a valid subset cannot be found
if (maxSum < s)
{
return;
}

// Add current number to the subset
var x = this.Elements[subsetStartIndex];

// Recurse through the sub-problem to the right
this.ScanSubsets(subsetStartIndex + 1, k - 1, s - x.Number, subset, cb);

// Remove current number and continue loop
subset.RemoveAt(subset.Count - 1);
}
}

public sealed class SubsetElement
{

public SubsetElement(int number, int index)
{
this.Number = number;
this.Index = index;
}

public override string ToString()
{
return string.Format("{0}({1})", this.Number, this.Index);
}
}
}
``````

Usage and performance testing:

``````private static void Main()
{
var sw = Stopwatch.StartNew();
var puzzle = new Puzzle(new[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
});

puzzle.Solve(2, 17, PuzzleOnSubsetFound);

sw.Stop();
Console.WriteLine("Subsets found: " + _subsetsCount);
Console.WriteLine(sw.Elapsed);
}

private static int _subsetsCount;

private static void PuzzleOnSubsetFound(Puzzle.SubsetElement[] subset)
{
_subsetsCount++;
return; // Skip prints when speed-testing

foreach (var el in subset)
{
Console.Write(el.ToString());
Console.Write("  ");
}

Console.WriteLine();
}
``````

Output:

Each line is a found subset, numbers in () are the original index of the number used in the subset

14(60) 3(107)
14(60) 3(109)
14(60) 3(102)
13(59) 4(105)
13(59) 4(111)
12(64) 5(96)
12(64) 5(104)
12(64) 5(112)
12(64) 5(110)
12(65) 5(96)
12(65) 5(104)
12(65) 5(112)
12(65) 5(110)
11(100) 6(108)
11(100) 6(113)
11(61) 6(108)
11(61) 6(113)
11(92) 6(108)
11(92) 6(113)
11(62) 6(108)
11(62) 6(113)
11(99) 6(108)
11(99) 6(113)
9(103) 8(93)
9(103) 8(94)
9(103) 8(97)
9(103) 8(98)
9(103) 8(101)
Subsets found: 28
00:00:00.0017020 (measured when no printing is performed)

The higher k is, the more cutoffs can be made. This is when you'll see the major performance difference. Your current code (the recursive version) also performs significantly slower when s is goes higher.

With `k=5`, `s=60`
Your current code: found 45070 subsets in 2.8602923 seconds
My code: found 45070 subsets in 0.0116727 seconds
That is 99.6% speed improvement

``````class Puzzle
{

public Puzzle(int[] numbers)
{
// Set N and make Elements array
// (to remember the original index of each element)
this.N = numbers.Length;
this.Elements = new SubsetElement[this.N];

for (var i = 0; i < this.N; i++)
{
this.Elements[i] = new SubsetElement(numbers[i], i);
}

// Sort Elements descendingly by their Number value
Array.Sort(this.Elements, (a, b) => b.Number.CompareTo(a.Number));

// Save tail-sums to allow immediate access by index
// Allow immedate calculation by index = N, to sum 0
this._tailSums = new int[this.N + 1];
var sum = 0;

for (var i = this.N - 1; i >= 0; i--)
{
this._tailSums[i] = sum += this.Elements[i].Number;
}
}

public void Solve(int s, Action<SubsetElement[]> callback)
{
for (var k = 1; k <= this.N; k++)
this.Solve(k, s, callback);
}

public void Solve(int k, int s, Action<SubsetElement[]> callback)
{
this.ScanSubsets(0, k, s, new List<SubsetElement>(), callback);
}

private void ScanSubsets(int startIndex, int k, int s,
List<SubsetElement> subset, Action<SubsetElement[]> cb)
{
// No more numbers to add, and current subset is guranteed to be valid
if (k == 0)
{
// Callback with current subset
cb(subset.ToArray());
return;
}

// Sum the smallest k elements
var minSubsetStartIndex = this.N - k;
var minSum = this._tailSums[minSubssetStartIndex];

// Smallest possible sum is greater than wanted sum,
// so a valid subset cannot be found
if (minSum > s)
{
return;
}

// Find largest number that satisfies the condition
// that a valid subset can be found
minSum -= this.Elements[minSubsetStartIndex].Number;

// But remember the last index that satisfies the condition
var minSubsetEndIndex = minSubsetStartIndex;

while (minSubsetStartIndex > startIndex &&
minSum + this.Elements[minSubsetStartIndex - 1].Number <= s)
{
minSubsetStartIndex--;
}

// Find the first number in the sorted sequence that is
// the largest number we just found (in case of duplicates)
while (minSubsetStartIndex > startIndex &&
Elements[minSubsetStartIndex] == Elements[minSubsetStartIndex - 1])
{
minSubsetStartIndex--;
}

// [minSubsetStartIndex .. maxSubsetEndIndex] is the
// full range we must check in recursion

for (var subsetStartIndex = minSubsetStartIndex;
subsetStartIndex <= minSubsetEndIndex;
subsetStartIndex++)
{
// Find the largest possible sum, which is the sum of the
// k first elements, starting at current subsetStartIndex
var maxSum = this._tailSums[subsetStartIndex] -
this._tailSums[subsetStartIndex + k];

// The largest possible sum is less than the wanted sum,
// so a valid subset cannot be found
if (maxSum < s)
{
return;
}

// Add current number to the subset
var x = this.Elements[subsetStartIndex];

// Recurse through the sub-problem to the right
this.ScanSubsets(subsetStartIndex + 1, k - 1, s - x.Number, subset, cb);

// Remove current number and continue loop
subset.RemoveAt(subset.Count - 1);
}
}

public sealed class SubsetElement
{

public SubsetElement(int number, int index)
{
this.Number = number;
this.Index = index;
}

public override string ToString()
{
return string.Format("{0}({1})", this.Number, this.Index);
}
}
}
``````

``````private static void Main()
{
var sw = Stopwatch.StartNew();
var puzzle = new Puzzle(new[]
{
7, 286, 200, 176, 120, 165, 206, 75, 129, 109,
123, 111, 43, 52, 99, 128, 111, 110, 98, 135,
112, 78, 118, 64, 77, 227, 93, 88, 69, 60,
34, 30, 73, 54, 45, 83, 182, 88, 75, 85,
54, 53, 89, 59, 37, 35, 38, 29, 18, 45,
60, 49, 62, 55, 78, 96, 29, 22, 24, 13,
14, 11, 11, 18, 12, 12, 30, 52, 52, 44,
28, 28, 20, 56, 40, 31, 50, 40, 46, 42,
29, 19, 36, 25, 22, 17, 19, 26, 30, 20,
15, 21, 11, 8, 8, 19, 5, 8, 8, 11,
11, 8, 3, 9, 5, 4, 7, 3, 6, 3,
5, 4, 5, 6
});

puzzle.Solve(2, 17, PuzzleOnSubsetFound);

sw.Stop();
Console.WriteLine("Subsets found: " + _subsetsCount);
Console.WriteLine(sw.Elapsed);
}

private static int _subsetsCount;

private static void PuzzleOnSubsetFound(Puzzle.SubsetElement[] subset)
{
_subsetsCount++;
return; // Skip prints when speed-testing

foreach (var el in subset)
{
Console.Write(el.ToString());
Console.Write("  ");
}

Console.WriteLine();
}
``````

14(60) 3(107)
14(60) 3(109)
14(60) 3(102)
13(59) 4(105)
13(59) 4(111)
12(64) 5(96)
12(64) 5(104)
12(64) 5(112)
12(64) 5(110)
12(65) 5(96)
12(65) 5(104)
12(65) 5(112)
12(65) 5(110)
11(100) 6(108)
11(100) 6(113)
11(61) 6(108)
11(61) 6(113)
11(92) 6(108)
11(92) 6(113)
11(62) 6(108)
11(62) 6(113)
11(99) 6(108)
11(99) 6(113)
9(103) 8(93)
9(103) 8(94)
9(103) 8(97)
9(103) 8(98)
9(103) 8(101)
Subsets found: 28
00:00:00.0017020 (measured when no printing is performed)

With `k=5`, `s=60`
Your current code: found 45070 subsets in 2.8602923 seconds
My code: found 45070 subsets in 0.0116727 seconds
That is 99.6% speed improvement

Simply search for all combinations of size K, and check each if it satisfies the condition.

The fastest algorithm for k combinations, suiting your case, would be:

``````for (var i1 = 0; i1 <= n; i1++)
{
for (var i2 = i1 + 1; i2 <= n; i2++)
{
for (var i3 = i2 + 1; i3 <= n; i3++)
{
...

for (var ik = iOneBeforeK + 1; ik <= n; ik++)
{
if (arr[i1] + arr[i2] + ... + arr[ik] == sum)
{
// this is a valid subset
}
}
}
}
}
``````

But you are talking about numbers and summing them up, meaning you could make cutoffs with a smarter algorithm.

Since all numbers are positive, you know that if a single number is big enough, you cannot add to it any more positive numbers and have it sum up to s. Given s=6 and k=4, the highest number to include in the search is s-k+1=3. 3+1+1+1 is k numbers, 1 being your lowest possible number, sums up to 6. Any number above 3 couldn't have 3 other positives added to it, and have the sum <= 6.

But wait, your minimum possible value isn't 1, it is 3. That's even better. So assume k=10, n=60,

K组合的最快的算法，适合你的情况，会：

``````for (var i1 = 0; i1 <= n; i1++)
{
for (var i2 = i1 + 1; i2 <= n; i2++)
{
for (var i3 = i2 + 1; i3 <= n; i3++)
{
...

for (var ik = iOneBeforeK + 1; ik <= n; ik++)
{
if (arr[i1] + arr[i2] + ... + arr[ik] == sum)
{
// this is a valid subset
}
}
}
}
}
``````

c#  algorithm  .net-2.0  dynamic-programming  subset-sum