代码随想录算法训练营第二十八天| 78 子集 90 子集|| 93 复原IP地址
78 子集
由题意可知数组中的元素互不相同，所以在dfs中我们可以将当前的path直接加入到res中。
class Solution {List<List<Integer>>res = new ArrayList<>();List<Integer>path = new LinkedList<>();public List<List<Integer>> 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<List<Integer>>res = new ArrayList<>();List<Integer>path = new LinkedList<>();public List<List<Integer>> 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)