Deadly Nicotine - 1 year ago 59

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.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**