代码随想录算法训练营第二十八天| 78 子集 90 子集|| 93 复原IP地址

78 子集

由题意可知数组中的元素互不相同，所以在dfs中我们可以将当前的path直接加入到res中。 

class Solution {
    List>res = new ArrayList<>();
    Listpath = new LinkedList<>();
    public List> subsets(int[] nums) {
        dfs(0,nums);
        return res;
    }
    private void dfs(int cnt,int[] nums){
        res.add(new LinkedList(path));
        for(int i = cnt;i < nums.length;i++){
            path.add(nums[i]);
            dfs(i + 1,nums);
            path.remove(path.size() - 1);
        }
    }
}

时间复杂度O(n×)

空间复杂度O(n)

90 子集||

class Solution {
    List>res = new ArrayList<>();
    Listpath = new LinkedList<>();
    public List> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(0,nums);
        return res;
    }
    private void dfs(int cnt,int nums[]){
        res.add(new LinkedList(path));
        for(int i = cnt;i < nums.length;i++){
            if(i > cnt && nums[i] == nums[i - 1])continue;
            path.add(nums[i]);
            dfs(i + 1,nums);
            path.remove(path.size() - 1);
        }
    }
}

时间复杂度O(n×)

空间复杂度O(n)

93 复原IP地址