Problem 43. Subset Sum

Created by Cody Team

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ >> v = [2, 3, 5];\n >> n = 8;\n >> subset_sum(v, n)\n ans =\n      2     3]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

4733 Solutions
1664 Solvers

Last Solution submitted on Sep 20, 2023

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

Show comments

Problem Recent Solvers1664

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 43. Subset Sum

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers1664

Suggested Problems

More from this Author96

Problem Tags

Community Treasure Hunt

Problem 43. Subset Sum

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers1664

Suggested Problems

More from this Author96

Problem Tags

Community Treasure Hunt

Players