78.Subsets

This question on LeetCode is a similar question to the Permutations question I did yesterday. But it is more tricky and interesting to solve it. Today is totally another brainstorming day.

Question

Solution

Backtracking

This approach generates all possible subsets of nums by considering whether or not to include each element in the subset. The time complexity of this algorithm is O(2^N), where N is the length of the input array, since there are 2^N possible subsets.

//  O(2^N)
class Solution {
    private List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> subsets(int[] nums) {
        helper(nums, 0, new ArrayList<>());
        return res;
    }

    private void helper(int[] nums, int index, List<Integer> list) {
        if(index >= nums.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        list.add(nums[index]);
        helper(nums, index + 1, list);

        list.remove(list.size()-1);
        helper(nums, index + 1, list);
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), res);
        return res;
    }
    
    private void backtrack(int[] nums, int start, List<Integer> curr, List<List<Integer>> res) {
	// Eveytime we add curr into res even if curr is empty list
        res.add(new ArrayList<>(curr));
	// use i=start to avoid containing duplicate subsets
        for (int i = start; i < nums.length; i++) {
            curr.add(nums[i]);
            backtrack(nums, i + 1, curr, res);
            curr.remove(curr.size() - 1);
        }
    }
}

Brute force

At first, I thought this solution was lousy…and I got the Time Limit Exceeded.

class Solution {
    private List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> subsets(int[] nums) {
        helper(nums, new ArrayList<Integer>());
        return res;
    }

    private void helper(int[] nums, List<Integer> list) {
        if(list.size() > nums.length) {
            return;
        }
        if(isNotExist(list)) {
            res.add(new ArrayList(list));
        }

        for(int i=0;i<nums.length;i++) {
            if(!list.contains(nums[i])) {
                list.add(nums[i]);
                helper(nums, list);
                list.remove(list.size()-1);
            }
        }
    }

    private boolean isNotExist(List<Integer> subList) {
        for(List<Integer> list:res) {
            if(list.size() == subList.size()) {
                boolean isSame = true;
                for(int i:list) {
                    if(!subList.contains(i)) {
                        isSame = false;
                        break;
                    }
                }
                if(isSame) {
                    return false;
                }
            }
        }

        return true;
    }
}