Problem 43. Subset Sum
Given a vector v of integers and an integer n, return the the indices of v (as a row vector in ascending order) that sum to n. If there is no subset in v that sums to n, return an empty matrix []. You can assume that the answer will always be unique.
Example:
>> v = [2, 3, 5]; >> n = 8; >> subset_sum(v, n) ans = 2 3
Solution Stats
Problem Comments
-
4 Comments
The combntns(eg.combntns(some_vector,i)) function throws:
Error: Undefined function 'combntns' for input arguments of type 'double'
But on my machine it takes i as a double. It even throws it if I cast i to int8.
Use nchoosek instead of combnts or combnk
At first I thought that it was quite difficult to look for the sets of elements of any size (sets of 1 element, 2 elements and so on), but then I realised that any selection of the vector elements correspond to a binary code ('1' for selecting that element and '0' for not selecting it). To select all possible elements combinations I only need to use the binary code from 1 to 2^(1+length(v))-1.
At first I thought that it was quite difficult to look for the sets of elements of any size (sets of 1 element, 2 elements and so on), but then I realised that any selection of the vector elements correspond to a binary code ('1' for selecting that element and '0' for not selecting it). To select all possible elements combinations I only need to use the binary code from 1 to 2^(1+length(v))-1.
Solution Comments
Show commentsProblem Recent Solvers1899
Suggested Problems
-
Get the area codes from a list of phone numbers
1052 Solvers
-
516 Solvers
-
412 Solvers
-
1161 Solvers
-
7166 Solvers
More from this Author96
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!