Problem 43. Subset Sum

Created by Cody Team

Solve Later

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

Solve

Solution Stats

3198 Solutions
1004 Solvers

Last Solution submitted on Jun 04, 2020

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

Sebastian on 2 Sep 2013

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.

Daniel Pereira on 8 May 2014

Use nchoosek instead of combnts or combnk

Thonigon on 8 Mar 2016

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.

Thonigon on 8 Mar 2016

Solution Comments

Solution 2240315

2 Comments

2 Comments

Jaya Lee on 28 Apr 2020

why here comes an error as:
idx=logical(de2bi(todecimal(1:(2^l-1)),16));

when I wanna use command:
idx=logical(de2bi(todecimal(1:(2^l-1)),16));

my local matlab 2019b function well, but online project confuze me.

Jaya Lee on 28 Apr 2020

And I found that:
Others solution used dec2bin function, which has matlab document as the de2bi function, work out the same way, but maybe the compile problem here makes the different result of online systeerm to local solftware.

Solution 2001066

1 Comment

1 Comment

Payam Morsali on 3 Nov 2019

why this isn't working here?
it works on my laptop;
function ind = subset_sum(v,n)
k=dec2bin(0:2^length(v)-1);
b=k.*v;
l=find(sum(b')==n);
m=k(l,:).*(1:length(v));
ind=m(m>0);
end

Solution 1443493

1 Comment

1 Comment

Jay on 18 Feb 2018

nchoosek function is fantastic!

Solution 1163369

2 Comments

2 Comments

David Verrelli on 14 Apr 2017

So apparently this is failing because my empty matrix is
1×0 (size 0) double
but Test Case 3 requires an empty matrix that is
0×0 (size 0) double
Hmmmm....

David Verrelli on 14 Apr 2017

So apparently this is failing because my empty matrix is 1×0 (size 0) double but Test Case 3 requires an empty matrix that is 0×0 (size 0) double Hmmmm....
[Subsequently amended to pass the test suite as Solution 1163376.]

Solution 1024612

1 Comment

1 Comment

yao gang on 20 Oct 2016

While I think I should have a rest and think more....

Solution 810099

2 Comments

2 Comments

Fabio on 19 Jan 2016

I really don't understand why, without the last three rows, it works for every test but the third.

Jan Orwat on 20 Jan 2016

compare the size(...) of the output with and without those lines and you will find out why :-)

Solution 435022

2 Comments

2 Comments

Pascal Geschwill on 24 Apr 2014

What am I doing wrong? If I enter the code on my computer, I am getting the correct solutions for the first and last case. I even cleared all other variables from the workspace.

Pascal Geschwill on 25 Apr 2014

Apparently I was using intersect wrong.

Solution 216498

1 Comment

1 Comment

danteliujie on 11 Mar 2019

great solution

Solution 125180

2 Comments

2 Comments

tqy on 8 Aug 2012

Why? I think my solution is right, but it always gives me a 'Fail'??? Can anyone help?

Ned Gulley on 8 Aug 2012

Take a look at your error messages. They are telling you that the function "combntns" is undefined. So it appears that you have this function on your computer, but it is not part of MATLAB and so Cody doesn't know what it is.

Solution 114145

1 Comment

1 Comment

li jian on 12 Dec 2012

artful solution.I can't think it out myself

Solution 114142

2 Comments

2 Comments

Cris Luengo on 17 Jul 2012

Is this a bug in MATLAB? v(c) == v(c') !!!

Cris Luengo on 17 Jul 2012

I mean, v(c) == v(c') if c is a vector. This is not true for a matrix c.

Solution 82441

1 Comment

1 Comment

Binbin Qi on 26 Apr 2012

why???

Solution 78038

1 Comment

1 Comment

Kye Taylor on 18 Apr 2012

Despite the warning, I'm stoked it worked.

{Warning: Concatenation involves an empty array with an
incorrect number of rows.
This may not be allowed in a future release.}

Solution 57544

1 Comment

1 Comment

Justin Winokur on 25 Jul 2013

well, I guess with Cody's way of scoring this would work, but honestly, a bit risky to use in "real life"

Solution 10043

1 Comment

1 Comment

Oleg Komarov on 27 Jan 2012

Buggy, mine is empty but with size, and doesn't get right answer.

Solution 1528

1 Comment

1 Comment

S L on 26 Jan 2012

only works for v > 0

Problem Recent Solvers1004

Problem Tags

matlab

Problem 43. Subset Sum

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers1004

Suggested Problems

More from this Author95

Problem Tags

Problem 43. Subset Sum

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers1004

Suggested Problems

More from this Author95

Problem Tags

Players