Return to Answer

Current code review:

1. (int)Math.pow(2,len) could be replaced with 1 << len;
2. Traverse binary representation of number without any other manipulations using bitwise and bit shift operators;

So, code can look like:

for (int i = 1; i < limit; i++) {
    int sum = 0;
    int cur = i;
    for (int j = 0; j < len; j++) {
        // tests if least significant bit is set
        if ((cur & 1) == 1) {
            sum += arr[j];
        }
        // shift to test next bit on next loop iteration
        cur = cur >> 1;
    }
    // do something with sum
}

About time complexity improvement:

In your case, for every subset of numbers, we count its sum from 'scratch', but, imagine we have two subsets - one includes 1st,3rd and 5th numbers, and second only 1st and 3rd. Knowing sum of first subset, we can easily evaluate sum of second: just add 5th number to it. So, think about following idea: make recursion function void getSums(int ind, int prevSum), where prevSum is that already precounted sum of some subset, which contains elements with index < ind. We start with getSums(0, 0) and then we have 2 choices: add element on ind index or not.

Code can look like:

void getSums(int ind, int prevSum) {
    if(id == arr.length) {
        sums.add(prevSum);
        return;
    }
    int sumIncludingInd = prevSum + arr[ind];        
    getSums(ind + 1, sumIncludingInd, sums, arr);
    int sumNotIncludingInd = prevSum;     
    getSUms(ind + 1, sumNotIncludingInd, sums, arr);
}

Time complexity in your case will be O(n * 2^n), since we have 2^n subsets and, to get the sum, n summing operations should be done. In recursive approach, on each step you need to do only one summing operation(or zero), which is O(1). So, overall time complexity will be O(2^n).

Current code review:

1. (int)Math.pow(2,len) could be replaced with 1 << len;
2. Traverse binary representation of number without any other manipulations using bitwise and bit shift operators;

So, code can look like:

for (int i = 1; i < limit; i++) {
    int sum = 0;
    int cur = i;
    for (int j = 0; j < len; j++) {
        // tests if least significant bit is set
        if ((cur & 1) == 1) {
            sum += arr[j];
        }
        // shift to test next bit on next loop iteration
        cur = cur >> 1;
    }
    // do something with sum
}

About time complexity improvement:

In your case, for every subset of numbers, we count its sum from 'scratch', but, imagine we have two subsets - one includes 1st,3rd and 5th numbers, and second only 1st and 3rd. Knowing sum of first subset, we can easily evaluate sum of second: just add 5th number to it. So, think about following idea: make recursion function void getSums(int ind, int prevSum), where prevSum is that already precounted sum of some subset, which contains elements with index < ind. We start with getSums(0, 0) and then we have 2 choices: add element on ind index or not.

Code can look like:

void getSums(int ind, int prevSum) {
    if(id == arr.length) {
        sums.add(prevSum);
        return;
    }
    int sumIncludingInd = prevSum + arr[ind];        
    getSums(ind + 1, sumIncludingInd, sums, arr);
    int sumNotIncludingInd = prevSum;     
    getSUms(ind + 1, sumNotIncludingInd, sums, arr);
}

Time complexity in your case will be O(n * 2ⁿ), since we have 2ⁿ subsets and, to get the sum, n summing operations should be done. In recursive approach, on each step you need to do only one summing operation(or zero), which is O(1). So, overall time complexity will be O(2ⁿ).

Current code review:

1. (int)Math.pow(2,len) could be replaced with 1 << len;
2. Traverse binary representation of number without any other manipulations using bitwise and bit shift operators;

So, code can look like:

for (int i = 1; i < limit; i++) {
    int sum = 0;
    int cur = i;
    for (int j = 0; j < len; j++) {
        // tests if least significant bit is set
        if ((cur & 1) == 1) {
            sum += arr[j];
        }
        // shift to test next bit on next loop iteration
        cur = cur >> 1;
    }
    // do something with sum
}

About time complexity improvement:

In your case, for every subset of numbers, we count its sum from 'scratch', but, imagine we have two subsets - one includes 1st,3rd and 5th numbers, and second only 1st and 3rd. Knowing sum of first subset, we can easily evaluate sum of second: just add 5th number to it. So, think about following idea: make recursion function void getSums(int ind, int prevSum), where prevSum is that already precounted sum of some subset, which contains elements with index < ind. We start with getSums(0, 0, sums) and then we have 2 choices: add element on ind index or not.

Code can look like(not including out of bounds checks and so on..):

void getSums(int ind, int prevSum) {
    int sumIncludingInd = prevSum + arr[ind];
    sums.add(sumIncludingInd);
    getSums(ind + 1, sumIncludingInd, sums, arr);
    int sumNotIncludingInd = prevSum;
     sums.add(sumNotIncludingInd);
    getSUms(ind + 1, sumNotIncludingInd, sums, arr);
}

Time complexity in your case will be O(n * 2^n), since we have 2^n subsets and, to get the sum, n summing operations should be done. In recursive approach, on each step you need to do only one summing operation(or zero), which is O(1). So, overall time complexity will be O(2^n).

Current code review:

1. (int)Math.pow(2,len) could be replaced with 1 << len;
2. Traverse binary representation of number without any other manipulations using bitwise and bit shift operators;

So, code can look like:

for (int i = 1; i < limit; i++) {
    int sum = 0;
    int cur = i;
    for (int j = 0; j < len; j++) {
        // tests if least significant bit is set
        if ((cur & 1) == 1) {
            sum += arr[j];
        }
        // shift to test next bit on next loop iteration
        cur = cur >> 1;
    }
    // do something with sum
}

About time complexity improvement:

In your case, for every subset of numbers, we count its sum from 'scratch', but, imagine we have two subsets - one includes 1st,3rd and 5th numbers, and second only 1st and 3rd. Knowing sum of first subset, we can easily evaluate sum of second: just add 5th number to it. So, think about following idea: make recursion function void getSums(int ind, int prevSum), where prevSum is that already precounted sum of some subset, which contains elements with index < ind. We start with getSums(0, 0) and then we have 2 choices: add element on ind index or not.

Code can look like:

void getSums(int ind, int prevSum) {
    if(id == arr.length) {
        sums.add(prevSum);
        return;
    }
    int sumIncludingInd = prevSum + arr[ind];        
    getSums(ind + 1, sumIncludingInd, sums, arr);
    int sumNotIncludingInd = prevSum;     
    getSUms(ind + 1, sumNotIncludingInd, sums, arr);
}

Time complexity in your case will be O(n * 2^n), since we have 2^n subsets and, to get the sum, n summing operations should be done. In recursive approach, on each step you need to do only one summing operation(or zero), which is O(1). So, overall time complexity will be O(2^n).

Current code review:

1. (int)Math.pow(2,len) could be replaced with 1 << len;
2. Traverse binary representation of number without any other manipulations using bitwise and bit shift operators;

So, code can look like:

for (int i = 1; i < limit; i++) {
    int sum = 0;
    int cur = i;
    for (int j = 0; j < len; j++) {
        // tests if least significant bit is set
        if ((cur & 1) == 1) {
            sum += arr[j];
        }
        // shift to test next bit on next loop iteration
        cur = cur >> 1;
    }
    // do something with sum
}

About time complexity improvement:

In your case, for every subset of numbers, we count its sum from 'scratch', but, imagine we have two subsets - one includes 1st,3rd and 5th numbers, and second only 1st and 3rd. Knowing sum of first subset, we can easily evaluate sum of second: just add 5th number to it. So, think about following idea: make recursion function void getSums(int ind, int prevSum), where prevSum is that already precounted sum of some subset, which contains elements with index < ind. We start with getSums(0, 0, sums) and then we have 2 choices: add element on ind index or not.

Code can look like(not including out of bounds checks and so on..):

void getSums(int ind, int prevSum) {
    int sumIncludingInd = prevSum + arr[ind];
    sums.add(sumIncludingInd);
    getSums(ind + 1, sumIncludingInd, sums, arr);
    int sumNotIncludingInd = prevSum;
    sums.add(sumNotIncludingInd);
    getSUms(ind + 1, sumNotIncludingInd, sums, arr);
}

Current code review:

1. (int)Math.pow(2,len) could be replaced with 1 << len;
2. Traverse binary representation of number without any other manipulations using bitwise and bit shift operators;

So, code can look like:

for (int i = 1; i < limit; i++) {
    int sum = 0;
    int cur = i;
    for (int j = 0; j < len; j++) {
        // tests if least significant bit is set
        if ((cur & 1) == 1) {
            sum += arr[j];
        }
        // shift to test next bit on next loop iteration
        cur = cur >> 1;
    }
    // do something with sum
}

About time complexity improvement:

In your case, for every subset of numbers, we count its sum from 'scratch', but, imagine we have two subsets - one includes 1st,3rd and 5th numbers, and second only 1st and 3rd. Knowing sum of first subset, we can easily evaluate sum of second: just add 5th number to it. So, think about following idea: make recursion function void getSums(int ind, int prevSum), where prevSum is that already precounted sum of some subset, which contains elements with index < ind. We start with getSums(0, 0, sums) and then we have 2 choices: add element on ind index or not.

Code can look like(not including out of bounds checks and so on..):

void getSums(int ind, int prevSum) {
    int sumIncludingInd = prevSum + arr[ind];
    sums.add(sumIncludingInd);
    getSums(ind + 1, sumIncludingInd, sums, arr);
    int sumNotIncludingInd = prevSum;
    sums.add(sumNotIncludingInd);
    getSUms(ind + 1, sumNotIncludingInd, sums, arr);
}

Time complexity in your case will be O(n * 2^n), since we have 2^n subsets and, to get the sum, n summing operations should be done. In recursive approach, on each step you need to do only one summing operation(or zero), which is O(1). So, overall time complexity will be O(2^n).