Problem 660. Find a subset that divides the vector into equal halves

Created by Ned Gulley

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 x, return the indices to elements that will sum to exactly half of the sum of all elements.</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[ Input  x  = [1 2 3 4 5 6 7]\n Output xi = [1 6 7]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>because</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ sum(x) = 28\n sum(x([1 6 7])) = 14]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The answer is not necessarily unique and the order is unimportant. We will just test to make sure that</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>sum(x)/2</w:t></w:r><w:r><w:t> is</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>sum(x(xi))</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

1993 Solutions
372 Solvers

Last Solution submitted on Mar 02, 2023

Last 200 Solutions

Problem Comments

14 Comments

14 Comments

Show 11 older comments

AMITAVA BISWAS on 11 Jun 2012

Could you please post the link to ASEE Challenge June 10-13? Thanks!

Ned Gulley on 14 Jun 2012

Amitava, do you mean here? The link is http://www.mathworks.com/matlabcentral/cody/?sort=created+desc&term=group%3A%22ASEE+Challenge%22

Vieniava on 6 Dec 2012

it seems that tests no3 and no4 are incorrectly defined. Ned, check this out please.

Ned Gulley on 7 Dec 2012

@Vieniava, can you be more specific? The tests are the same in all cases. I did verify that Solution 173962 does indeed get an incorrect answer to tests 3 and 4.

Ted on 16 Mar 2013

This was fun

Jean-Marie Sainthillier on 17 Mar 2013

A lot a very beautiful solutions.

J.R.! Menzinger on 18 Nov 2013

What was changed on 5th. November?? :-/

Ned Gulley on 19 Nov 2013

I added a new test. I periodically strengthen test suites to defeat look-up table strategies.

Aryaa Ravieshancar on 2 Feb 2014

I solved this with matlab inbuilt function 'combnk'. Is that not allowed? It gives me the error 'Undefined function' everytime I run my solution.

Ned Gulley on 3 Feb 2014

Aryaa: Your solution looks good. The problem is that combnk is in the Statistics Toolbox, and Cody is designed to use only functions from basic MATLAB.

Hassan Dehghani on 5 Apr 2014

I used random numbers, but couldn't get it. :( (worked fine in my laptop.) :( I guess I haven't completely understood the question. :((

Hassan Dehghani on 7 Apr 2014

why do i get internal server error :(((

Ned Gulley on 8 Apr 2014

Hassan, where are you getting an internal server error? Maybe leave your comment on the solution that has the related error? I'm guessing that your solution relies on randomness, so if you don't get lucky, the answer will time out. You may get lucky on your computer, but not on the Cody server.

John D'Errico on 22 Aug 2016

A basic one liner with intlinprog, but not an option in Cody. :)

Solution Comments

Solution 9420073

Solution 1620676

1 Comment

1 Comment

NZMarkW on 3 Sep 2018

This problems keeps giving me:
While evaluating the solution, the server encountered an error caused by temporary unavailability of MATLAB Service. Wait a few minutes for the MATLAB Service to return, and then rescore.
ONLY this problem????

Solution 1615025

1 Comment

1 Comment

Bhaskar R on 23 Aug 2018

My solution works for all combinations but test case is not designed well

Solution 1279326

1 Comment

1 Comment

Informaton on 1 Oct 2017

Because the two line version runs out of memory with dec2bin ...

Solution 1279323

1 Comment

1 Comment

Informaton on 1 Oct 2017

Ha! Out of memory error for matrix multiplication :)

Solution 940169

1 Comment

1 Comment

John D'Errico on 22 Aug 2016

(lol) An expectedly poor score, but still fun to write it in recursive form. Accomplished by adding spare arguments both as input to and output from split_it, then calling split_it recursively as needed.

Solution 655485

2 Comments

2 Comments

Ramoflaple on 12 Aug 2015

smart cheater :)

danteliujie on 8 Apr 2019

cool

Solution 477396

1 Comment

1 Comment

Kirk on 23 Jul 2014

Would be much harder problem if you did not allow repeated index numbers and insisted on numerical index instead of logical

Solution 401941

3 Comments

3 Comments

George Berken on 12 Feb 2014

combnk is not accepted ! ! !
nchoosek works :)

Ramoflaple on 12 Aug 2015

Should this work for the last test!!!
why does the error "out of memory" not show?

Peng Liu on 25 Apr 2016

Because once found, the function returns, thus diminishing the possibility of large I

Solution 395052

1 Comment

1 Comment

nimin bbs on 31 Jan 2014

This is not the shortest, but it is a oneliner.

Solution 259636

1 Comment

1 Comment

Thomas Vanaret on 30 Oct 2013

Only allowed by a too simple test suite...

Solution 226968

1 Comment

1 Comment

Thomas Vanaret on 30 Oct 2013

This should be the best noted solution :
- No brute-force search
- No "regexp" trick
- No cheating (allowed by a too simple test suite)

Solution 207993

2 Comments

2 Comments

Jean-Marie Sainthillier on 17 Mar 2013

Wonderful solution with a factorization of ans.

Ramoflaple on 12 Aug 2015

make full use of "half of the sum"

Problem Recent Solvers372

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 660. Find a subset that divides the vector into equal halves

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers372

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 660. Find a subset that divides the vector into equal halves

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers372

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players