java - 子集数

Question

class Solution {
    int f(int[] a, int s, int n) {
        if (n == 0)
            return s;
        return f(a, s + 1, n - 1) + f(a, s, n - 1);
    }
}

class Test {
    public static void main(String[] args) {
        int[] a = { 1, 1, 2, 3 };
        System.out.println(new Solution().f(a, 0, a.length));
    }
} 

我编写了一个代码来打印子集的数量，在每个索引处，我有两个选择是否将 a[i] 包含在子集中，因为每当要包含元素时，我都会向 s 添加 1，但这种方法给出了错误的答案。为什么是错误的？

Answer 1

Math.pow(2, a.length) 

将是明显的解决方案。但如果你真的想以这种方式找到它，它应该“return 1”而不是“return s”，因为每次它到达零时，就意味着没有留下任何元素，因此是空列表，因此是1。