leetcode题目 78. 子集&&90. 子集 II

题目(78. 子集)

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

思路

进行递归回溯，对每个元素我们有两种选择，要或者不要，选择了之后进入下一个递归。

代码

public class problem78 {
	public List<List<Integer>> subsets(int[] nums) {
		List<List<Integer>> res=new ArrayList<List<Integer>>();
		
		back(0, new ArrayList(), res,nums);
		
        return res;
    }
	
	public void back(int index,List<Integer> list,List<List<Integer>> res,int[] nums){
		if(index==nums.length){
			res.add(new ArrayList<>(list));
			return;
		}
		
		list.add(nums[index]);
		back(index+1, list, res, nums);
		
		//回溯
		list.remove(list.size()-1);
		back(index+1, list, res, nums);
		
	}
	
	public static void main(String[] args) {
		problem78 pro=new problem78();
		int[] nums={1,2,3};
		List<List<Integer>> list=pro.subsets(nums);
		for(int i=0;i<list.size();i++){
			for(int j=0;j<list.get(i).size();j++){
				System.out.print(list.get(i).get(j)+" ");
			}
			System.out.println();
		}
	}
}

题目(90. 子集 II)

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例

输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

思路

我们先对输入数组进行排序，然后进行递归，每次递归时我们计算一下当前元素有多少个(size)，选择策略为选择0个到size个，每选择一次进入下一个递归，注意标计当前位置的指针index需要直接跳到下一类元素的位置，同样，这里也需要进行回溯。

代码

public class problem90 {
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		List<List<Integer>> res=new ArrayList<List<Integer>>();
		
		Arrays.sort(nums);
		
		back(0, new ArrayList(), res,nums);
		
		return res;
    }
	
	//index标计当前位置
	public void back(int index,List<Integer> list,List<List<Integer>> res,int[] nums){
		if(index>=nums.length){
			res.add(new ArrayList<>(list));
			return;
		}
		
		int size=1;
		for(int i=index;i+1<nums.length;i++){
			if(nums[i]==nums[i+1])
				size++;
			else
				break;
		}
//		System.out.println("yy"+size+" "+nums[index]);
		
		//进行循环，每次加入不同个数的相同元素
		for(int i=0;i<=size;i++){
			if(i==0)
				back(index+size, list, res, nums);
			else{
				list.add(nums[index]);
				back(index+size, list, res, nums);
			}
		}
		
		//回溯
		for(int i=0;i<size;i++){
			list.remove(list.size()-1);
		}
		
	}
	
	public static void main(String[] args) {
		problem90 pro=new problem90();
		int[] nums={1,2,2};
		List<List<Integer>> list=pro.subsetsWithDup(nums);
		for(int i=0;i<list.size();i++){
			for(int j=0;j<list.get(i).size();j++){
				System.out.print(list.get(i).get(j)+" ");
			}
			System.out.println();
		}
	}
}