0
\$\begingroup\$

For an array of length n, the possible number of subsets is Math.pow(2, n). for each value between 0 and Math.pow(2, n), see the index at which the bit is set, and include the corresponding number in the given input to the current subset.

public List<List<Integer>> subsets(int[] nums){
        int numOfSubSets = 1 << nums.length;
        List<List<Integer>> subsets = new ArrayList<>();
        int index = -1;
        subsets.add(new ArrayList<>());
        List<Integer> tempSubset;
        int current = 0;
        for(int i = 1 ; i < numOfSubSets ; i++ ){
            index = -1;
            tempSubset = new ArrayList<>();
            current = i;
            while(current != 0){
                index++;
                if((current & 1) != 0){
                    tempSubset.add(nums[index]);
                }
                current = current >> 1;
            }
            subsets.add(tempSubset);
        }
        return subsets;
    }
\$\endgroup\$
  • \$\begingroup\$ What is the question? \$\endgroup\$ – user unknown Mar 26 '18 at 21:42
2
\$\begingroup\$
  • Your code contains some unnecessary assignments, where the value assigned to a variable is never used before it is being overwritten. These are the first assignment of index in the line int index = -1; and the first assignment of current in the line int current = 0;. With the assignments gone, only the declarations int index and int current are left, and since it generally makes code easier to understand to reduce the scope of variables to the smallest possible extent and to keep them out of places where they are not needed, I suggest you move the declarations of these variables inside the for loop, since they are not needed outside it and don't need to keep their value from one loop iteration to the next, as they are assigned a new value at the beginning of each loop iteration. The same goes for the variable tempSubset.
  • You are treating the empty subset as a special case by adding it manually before the for loop and then initializing i to 1 instead of 0. However, this is not necessary. The code would work just as well if you removed the line subsets.add(new ArrayList<>()); and initialized i to 0. This would not only save one line of code, but with one algorithm that works for all cases, and not only for all cases except one, the code will be easier to understand.
  • A for loop might be more fitting for what your are doing with a while loop. Instead of this:

    index = -1;
    tempSubset = new ArrayList<>();
    current = i;
    while(current != 0){
        index++;
        if((current & 1) != 0){
            tempSubset.add(nums[index]);
        }
        current = current >> 1;
    }
    subsets.add(tempSubset);
    

    You could do this:

    tempSubset = new ArrayList<>();
    for (int index = 0; (i & 0xFFFFFFFF << index) != 0; index++) {
        if ((i & 1 << index) != 0) {
            tempSubset.add(nums[index]);
        }
    }
    

After these changes, your code will look like this:

public List<List<Integer>> subsets(int[] nums){
    int numOfSubSets = 1 << nums.length;
    List<List<Integer>> subsets = new ArrayList<>();

    for(int i = 0; i < numOfSubSets; i++){
        List<Integer> tempSubset = new ArrayList<>();
        for (int index = 0; (i & 0xFFFFFFFF << index) != 0; index++) {
            if ((i & 1 << index) != 0) {
                tempSubset.add(nums[index]);
            }
        }
        subsets.add(tempSubset);
    }
    return subsets;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.