I have given an array.And i want to find the all permutation of an array so it sum to a specific numbers.
ExampleArray a =[2,3,5 ,1]
Target = 8
`Solution: [2,2,2,2] ,[5,3] ,[3,3,2] ,[5,2,1] and all possible combination
Please provide me a approach to solve this the problem , the problem i am facing how to handle the repetition of the elements.Target is a large number of 10^6.
I think it is same asThis theory
Asked
Active
Viewed 765 times
3
Bad Coder
- 866
- 1
- 12
- 27
-
2This is sometimes called the coin changing problem and is a standard algorithms question. You may have more luck searching for that term. – templatetypedef Sep 10 '14 at 19:25
-
Thanks all of you i have found that it is a standard algorithm will be posting my solution soon – Bad Coder Sep 10 '14 at 20:15
-
What about `[5,1,1,1]`, `[3,3,1,1]`, `[3,2,1,1,1]` and `[1,1,1,1,1,1,1,1]`, and [many more]? – tobias_k Sep 10 '14 at 20:15
-
@tobias_k please go through [this](http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/) – Bad Coder Sep 10 '14 at 20:16
-
No thanks. Why don't you just explain in your question why it's okay to have 4x2 but not 8x1 or 2x3+2x1? – tobias_k Sep 10 '14 at 20:18
-
@tobias_k ya it was my mistake i realized that thanks for pointing out – Bad Coder Sep 10 '14 at 20:19
-
a little help what if the order matter i.e [2,3] and [3,2] are different – Bad Coder Sep 10 '14 at 21:30
1 Answers
1
You are facing a typical Subset Problem. The worst case complexity of this problem is exponential no matter how you put it. You might find good polynomial-time approximations that work wonders for average case though.
Ajk_P
- 1,874
- 18
- 23