Sign up ×

I'm trying the classic subset sum problem on an online judge. However, the difference this time is that n<=30 so the maximum operations can go up to 30*2^30. I already have some working code below. However, the time limit of the program is 1 second and my program hovers between 0.5 to 1.1 seconds. This results in a TLE although I've tried to speed up my code as best as I can. Do you guys have any tips on how I might be able to speed up and optimise my code further? Thanks in advance.

#include <iostream>
#include <cstdio>
using namespace std;

unsigned power(unsigned x, unsigned y){        //pow function
    unsigned sum=x;
    for (int i=1;i<=y-1;i++)
    return sum;

int main(){
    unsigned t, n, p, sum, sum2, tmpsum=0;
    unsigned bars[32];
    bool found;
    scanf("%u", &t);
    while (t--){
        scanf("%u %u", &n, &p);
        if (tmpsum<n)found=false;
        unsigned end=power(2,p)-1;          //counting from the end and from the start
        for (unsigned i=0;i<power(2,p)&&tmpsum>=n;i++){       //counting from 1 to 2^n in binary
            for (unsigned j=0;j<p;j++){
                if (i&(1<<j))
                if (end&(1<<j))     //counting from the end and start at the same time
            if (sum==n||sum2==n)
share|improve this question

closed as off topic by Luchian Grigore, Toto, Hasturkun, alestanis, Kiril Kirov Feb 18 '13 at 11:45


You should post this question on instead. –  Joachim Pileborg Feb 18 '13 at 9:00
Man, the exponentiation function can be vastly improved. Look here for more information:… –  AraK Feb 18 '13 at 9:01

7 Answers 7

up vote 2 down vote accepted

Writing ugly code doesn't make it faster, separate your statements onto different lines, i.e replace {sum2+=bars[j];end--;} with

    sum2 += bars[j];

On to the question: your major time loss is likely here:


Which will, unless you've got a particularly good compiler, be calculating power(2, p) once for every cycle through the loop, this is completely unneeded. Pre-calculate it.

int pow2p = power(2, p);
for (unsigned i=0;i<pow2p&&tmpsum>=n;i++){

Also, doing powers of 2 this way is very slow, so use << instead (1<<p == power(2, p)).

Edit Since this has been accepted, I'll collect together minor points from other answers/comments:

  1. As Nim points out, the tmpsum>=n check doesn't need to be done every loop as neither n nor tmpsum change during the loop.

  2. As Karthik T point out, the line if (tmpsum<n)found=false; is redundant, found can never be anything but false at this point.

share|improve this answer
One more thing to add, the check tmpsum>=n is redundant in that loop, neither appears to be touched in the loop, just rewrite the if condition about to bypass the loop.. –  Nim Feb 18 '13 at 9:26
also, use std::pow from <cmath> rather than hand-rolling, the compiler may optimize better for powers of two... –  Nim Feb 18 '13 at 9:28

Move power(2,p) outside the loop.

share|improve this answer
bit shift will be faster IMHO. –  Ivaylo Strandjev Feb 18 '13 at 8:59
@IvayloStrandjev both should happen for best results I expect. –  Karthik T Feb 18 '13 at 9:00

Use bit shift for computing degrees of two.

share|improve this answer

In addition to what others have said, Avoid Branching. For example:

if (i&(1<<j))

can be written as

sum+=bars[j] * ((i&(1<<j))>>j);

Granted, it makes already hard to read code even harder to read.

share|improve this answer
if (tmpsum<n)found=false;

This line achieves nothing, found is already false.


Is being calculated twice, can be reduced to once by storing the result.

share|improve this answer
It's unlikely that the compiler won't already cache 1<<j. –  Jack Aidley Feb 18 '13 at 9:06

for starters you can move power(2,p) out of the for loop

for (unsigned i=0, end=power(2,p); i<end && tmpsum>=n; i++)
share|improve this answer
  1. power(2, p) is equal to 1 << p
  2. Define sum and sum2 as register variables.

    register unsigned sum, sum2;

share|improve this answer
Register is very, very unlikely to make any difference at all. –  Jack Aidley Feb 18 '13 at 9:04
Unless this is Turbo C++ or some other 20 year-old compiler, the use of register will have near zero effect - if it has any effect at all, it's just as likely to be detrimental as it is to be good. Modern compilers, such as gcc later than (at least) 2.95 [the latest released version is 4.8 or so] will use registers whether you ask for it or not whenever possible. –  Mats Petersson Feb 18 '13 at 9:04
