My JAVA non-recursive solution


  • 0
    Q

    The basic idea is (take input [1, 2, 3] for example) : let suppose there is a bit representative "xxx" 0 for not take the value and 1 for taking the value. In other word:
    000 -> []
    001 -> [3] (take the third value)
    010 -> [2]
    011 -> [2, 3]
    100 -> [1]
    101 -> [1, 3]
    110 -> [1, 2]
    111 -> [1, 2, 3]
    And it's quite clear that all these are bit representative of value from 0 to 2^nums.lenght - 1. And so we can solve the problem.

    Here is my code. (The function generateSubset need further simplifying)

        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            int limit = (int)Math.pow(2, nums.length);
    
            for(int i = 0; i < limit; i++){
                res.add(generateSubset(nums, i));
            }
            return res;
        }
         
        private List<Integer> generateSubset(int[] nums, int number){
            List<Integer> subList = new ArrayList<>();
            String bitStr = Integer.toBinaryString(number);
            int len = nums.length;
            int count = bitStr.length();
            while(count < len){
                bitStr = "0" + bitStr;
                count++;
            }
            for(int i = 0; i < len; i++){
                if(bitStr.charAt(i) == '1'){
                    subList.add(nums[i]);
                }
            }
            return subList;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.