Given an array (e.g. [1,2]) of n elements and a number 'k' (e.g. 6), find all possible ways to produce the sum = k
For given example answer would be 4 because
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
The algorithm I could think of is by brute force, we simulate all possible scenarios, and stop when from given state we can not reach result.
arr[] = [1,2]
k = 6
globalCount =0;
function findSum(arr,k)
{
if(k ==0)
globalCount++
return
else if(k<0)
return
for each i in arr{
arr.erase(i)
tmp = k
findSum(arr,tmp)
while(k>=0){
findSum(arr,tmp -= i)
}
}
I am not sure if my solution is most efficient one out there. Please comment /correct or show pointers to better solutions.
EDIT : Would really appreciate if someone can give me runtime complexity of my code and their soln code. :) Mine code complexity I think is Big-O( n^w ) w = k/avg(arr[0]..arr[n-1])
If you're willing to excuse the fancy linq tricks, you might find this C# solution useful. Fortunately linq reads kind of like english. The idea is to build up the solutions as k
starts from 0 and increments until it reaches its correct value. Each value of k
builds on the previous solutions. One thing you have to watch for though is to ensure that the new "ways" you're finding are not re-orderings of others. I solved that by only counting them as valid if they're sorted. (which was only a single comparison)
void Main() {
foreach (int[] way in GetSumWays(new[] {1, 2}, 6)) {
Console.WriteLine (string.Join(" ", way));
}
}
int[][] GetSumWays(int[] array, int k) {
int[][][] ways = new int[k + 1][][];
ways[0] = new[] { new int[0] };
for (int i = 1; i <= k; i++) {
ways[i] = (
from val in array
where i - val >= 0
from subway in ways[i - val]
where subway.Length == 0 || subway[0] >= val
select Enumerable.Repeat(val, 1)
.Concat(subway)
.ToArray()
).ToArray();
}
return ways[k];
}
Output:
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
It uses a dynamic programming approach and should be faster than a naive recursive approach. I think. I know it's fast enough to count the number of ways to break a dollar in a few milliseconds. (242)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With