dp系列之子集系列

数据结构动态规划
dp系列, 数据结构, 高频面试题总结

1. 子集

题目详情

给定一个含不同整数的集合，返回其所有的子集
样例：
如果 S = [1,2,3]，有如下的解：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

思路 – 递归解法

  • 深度优先搜索
  • 由于样例中的输出需要满足从小到大排列，所以在将数组传入helper()中时需要先对数组进行排序处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    /**
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        result.add(new ArrayList<Integer>(list));
        //为了使列表中的值按顺序排列
        Arrays.sort(nums);
        helper(result, list, nums, 0);
        
        return result;
    }
    
    private void helper(List<List<Integer>> result,
                        List<Integer> list,
                        int[] nums,
                        int index) {
        if (list.size() == nums.length) {
            return;
        }
        
        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            result.add(new ArrayList<Integer>(list));
            helper(result, list, nums, i+1);
            list.remove(list.size() - 1);
        }
        
    }
}

思路 – 非递归解法

  • n = nums.length, 1 << n = 2^n
  • each subset equals to an binary integer between 0 … 2^n - 1
1
2
3
4
5
0 - > 000 - > []
1 - > 001 - > [1]
2 - > 010 - > [2]
...
7 - > 111 - > [1, 2, 3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int n = S.length;
        Array.sort(S);
        for (int i = 0; i < (1 << n); i++) {
            ArrayList<Integer> subset = new ArrayList<Integer>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    subset.add(S[j]);
                }
            }
            result.add(subset);
        }
        
        return result;
    }
}

2. 带重复元素的子集

题目详情

给定一个可能具有重复数字的列表，返回其所有可能的子集

样例：
如果 S = [1,2,2]，有如下的解：

1
2
3
4
5
6
7
8
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

思路

  • 在dfs函数中的for循环里面加条语句即可

    1
    2
    if (i != index && nums[i] == nums[i-1])
                    continue;

  • 其余逻辑和不带重复元素的子集一样

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution {
    /**
     * @param nums: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // write your code here
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        result.add(new ArrayList<Integer>());
        Arrays.sort(nums);
        helper(result, list, nums, 0);
        
        return result;
                
    }
    
    private void helper(List<List<Integer>> result,
                        List<Integer> list,
                        int[] nums,
                        int index) {
                            
        if (list.size() == nums.length)
            return;
        
        for (int i = index; i < nums.length; i++) {
            
            if (i != index && nums[i] == nums[i-1])
                continue;
            
            list.add(nums[i]);
            result.add(new ArrayList<Integer>(list));
            helper(result, list, nums, i+1);
            list.remove(list.size() - 1);
            
        }
                            
    }
}
Compartir Comentarios