JAVA 3 Different Solutions.


  • 0
    T

    iterative

        public List<List<Integer>> subsets(int[] nums) {
            
            ArrayList<List<Integer>> ans = new ArrayList<>();
            if(nums.length == 0) return ans;
            
            ans.add(new ArrayList<>());
            
            for(int num: nums){
                int size = ans.size();
                for(int i = 0; i < size; i ++){
                    List<Integer> tmp = new ArrayList<>(ans.get(i));
                    tmp.add(num);
                    ans.add(tmp);
                }
            }
            
            return ans;
        }
    

    recursive

        public List<List<Integer>> subsets(int[] nums) {
            
            ArrayList<List<Integer>> ans = new ArrayList<>();
            if(nums.length == 0) return ans;
            
            List<Integer> sub = new ArrayList<>();
            dfs(nums, 0, sub, ans);
            return ans;
        }
        
        public void dfs(int[] nums, int start, List<Integer> sub, ArrayList<List<Integer>> ans) {
            
            if(start > nums.length)
                return;
            
            ans.add(new ArrayList<>(sub));
            
            for(int i = start; i < nums.length; i ++){
                sub.add(nums[i]);
                dfs(nums, i + 1, sub, ans);
                sub.remove(sub.size() - 1);
            }
        }
    

    bit manipulation

        public List<List<Integer>> subsets(int[] nums) {
            
            ArrayList<List<Integer>> ans = new ArrayList<>();
            if(nums.length == 0) return ans;
            
            int n = 1 << nums.length;
            for(int i = 0; i < n; i ++){
                ans.add(getSub(nums, i));
            }
            return ans;
        }
        
        public List<Integer> getSub(int[] nums, int k) {
            
            List<Integer> subs = new ArrayList<>();
            for(int i = 0; i < nums.length; i ++){
                
                if((k & (1 << i)) != 0)
                    subs.add(nums[i]);
            }
            return subs;
        }
    

  • 0
    T

    similar bit manipulation solution:

        public List<List<Integer>> subsets(int[] nums) {
            
            ArrayList<List<Integer>> ans = new ArrayList<>();
            if(nums.length == 0) return ans;
            
            int n = 1 << nums.length;
            for(int i = 0; i < n; i ++){
                ans.add(getSub(nums, i));
            }
            return ans;
        }
        
        public List<Integer> getSub(int[] nums, int k) {
            
            List<Integer> subs = new ArrayList<>();
            
            int index = 0;
            for(int i = k; i > 0; i = i>>1){
                
                if((i & 1) == 1)
                    subs.add(nums[index]);
                index++;
            }
            return subs;
        }
    

Log in to reply
 

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