循环和递归

Posted on

找出集合的子集，有重复元素的情况下。讨论区看到不同的代码，自己写的时候用第一种，在遍历下一个元素的时候用递归的方方式，这样比较慢。

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
public void helper(List<List<Integer>> res, List<Integer> each, int pos, int[] n) {
    if (pos <= n.length) {
        res.add(each);
    }
    int i = pos;
    while(i < n.length) {
        each.add(n[i]);
        helper(res, new ArrayList<>(each), i + 1, n);
        each.remove(each.size() - 1);
        i++;
        while (i < n.length && n[i] == n[i - 1]) {i++;}
        //helper(res,new ArrayList<>(each),i,n);
    }
    return;
}
和
public void helper(List<List<Integer>> res, List<Integer> each, int pos, int[] n) {
    if (pos == n.length) {
        res.add(each);
    }
    int i = pos;
    if(i < n.length) {
        each.add(n[i]);
        helper(res, new ArrayList<>(each), i + 1, n);
        each.remove(each.size() - 1);
        i++;
        while (i < n.length && n[i] == n[i - 1]) {i++;}
        helper(res,new ArrayList<>(each),i,n);
    }
    return;
}

上面两种方法的结果是一样的，第二个的思路很好理解，和无重复数字时的相同，一个数字要么加，要么不加，但是递归的次数要多一些，。而第一个方法递归次数和结果一样。第一个种方法是把不加的数字，在循环中跳过，而第二中通过递归来实现。第一个是先把集合找齐，然后一个个去掉数字进行实现。第二个是从一开始添加数字时就带或者不带进行选择，当遍历到最后的数字时，完成了。第二种方法快一点。