Deadly Nicotine Deadly Nicotine - 1 month ago 6
C# Question

Is there an efficient way to find all ordered arrangements of elements in the set S that add up to N?

Here's what I mean. Suppose

S = {1, 4}
and
N = 5
. The ordered arrangements of elements in the set
S
would be like

{1}, {4}, {1,1}, {1,4}, {4,1}, {4,4}, {1,1,1}, ....


and the ones that sum up to
N
are

{1,4}, {4, 1}, {1,1,1,1,1}


I want an algorithm that finds those efficiently.

My "brute force" way would be like

static IEnumerable<IEnumerable<int>> OrderedArrangements(IEnumerable<int> nums, int k)
{
var singles = nums.Select(i => new int[] {i} );
var cumulative = singles;
for(int j = 2; j <= k; ++j)
{
var last = cumulative.Where(list => list.Count() == (j - 1));
var next = from x in singles
from y in last
select x.Concat(y);
cumulative = cumulative.Concat(next);
}
return cumulative;
}


and then

int sumToN = OrderedArrangements(new int[] {1, 4}, N)
.Where(x => x.Sum() == N);


but I'm wondering if there's an obvious and more efficient way to do this.

Answer

Just in case the above answer isn't clear enough, you could try straight forward recursion e.g.

     ...
    /       \
   (1)     (4)          
  /  \     /  \
 (1)(4)   (1)(4)
static void f(int sum, int n, String str, int[] arr){
    if (n == sum){
        Console.WriteLine(str);
        return;
    }
    if (n > sum) return;
    for (int i = 0; i < arr.Length; i++){
        f(sum, n + arr[i], str + arr[i].ToString(), arr);
    }
}

static void Main(string[] args){
    int[] arr =  { 1, 4 };
    f(5, 0, "", arr);
}

Where sum is N in your question, n is initialized to 0, str is initialized to "" and arr is S in your question.

output:

11111
14
41