Deadly Nicotine - 6 months ago 34

C# Question

Here's what I mean. Suppose

`S = {1, 4}`

`N = 5`

`S`

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

and the ones that sum up to

`N`

`{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
```