Subsets

• 迭代版

Java

public class Solution {
    
    /*
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    public List<List<Integer>> subsets(int[] nums) {
        // List vs ArrayList （google）
        List<List<Integer>> results = new ArrayList<>();
        
        if (nums == null) {
            return results; // 空列表
        }
        
        Arrays.sort(nums);
        
        // BFS
        Queue<List<Integer>> queue = new LinkedList<>();
        queue.offer(new LinkedList<Integer>());
        
        while (!queue.isEmpty()) {
            List<Integer> subset = queue.poll();
            results.add(subset);
            
            for (int i = 0; i < nums.length; i++) {
                if (subset.size() == 0 || subset.get(subset.size() - 1) < nums[i]) {
                    List<Integer> nextSubset = new LinkedList<Integer>(subset);
                    nextSubset.add(nums[i]);
                    queue.offer(nextSubset);
                }
            }
        }
        return results;
    }
}

• 递归版

Java

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        result.add(path);
        helper(nums, path, result, 0);
        return result;
    }
    public void helper(int[]nums, List<Integer>path, List<List<Integer>> result, int start){
        for(int i = start; i < nums.length; i++){
            if(path.contains(nums[i])) continue;
            path.add(nums[i]);
            result.add(new ArrayList<>(path));
            helper(nums, path, result, i + 1);
            path.remove(path.size() - 1);
        }
    }
}