90. 子集 II

​ ​官方详细题解​​

回溯法

登录后复制

      
      

       
       class 
       
       Solution {
       
       
    
       
       public 
       
       List
       
       <
       
       List
       
       <
       
       Integer
       
       >> 
       
       subsetsWithDup(
       
       int[] 
       
       nums) {
       
       
    
       
       List
       
       <
       
       List
       
       <
       
       Integer
       
       >> 
       
       ans 
       
       = 
       
       new 
       
       ArrayList
       
       <>();
       
       
    
       
       Arrays.
       
       sort(
       
       nums); 
       
       //排序
       
       
    
       
       getAns(
       
       nums, 
       
       0, 
       
       new 
       
       ArrayList
       
       <>(), 
       
       ans);
       
       
    
       
       return 
       
       ans;
       
       
}
       
       

       
       

       
       private 
       
       void 
       
       getAns(
       
       int[] 
       
       nums, 
       
       int 
       
       start, 
       
       ArrayList
       
       <
       
       Integer
       
       > 
       
       temp, 
       
       List
       
       <
       
       List
       
       <
       
       Integer
       
       >> 
       
       ans) {
       
       
    
       
       ans.
       
       add(
       
       new 
       
       ArrayList
       
       <>(
       
       temp));
       
       
    
       
       for (
       
       int 
       
       i 
       
       = 
       
       start; 
       
       i 
       
       < 
       
       nums.
       
       length; 
       
       i
       
       ++) {
       
       
        
       
       //和上个数字相等就跳过
       
       
        
       
       if (
       
       i 
       
       > 
       
       start 
       
       && 
       
       nums[
       
       i] 
       
       == 
       
       nums[
       
       i 
       
       - 
       
       1]) {
       
       
            
       
       continue;
       
       
        }
       
       
        
       
       temp.
       
       add(
       
       nums[
       
       i]);
       
       
        
       
       getAns(
       
       nums, 
       
       i 
       
       + 
       
       1, 
       
       temp, 
       
       ans);
       
       
        
       
       temp.
       
       remove(
       
       temp.
       
       size() 
       
       - 
       
       1);
       
       
    }
       
       
}
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.