给一个数组, 求子集的个数, 要求是子集中的最小值+最大值小于给定target

    /**
     * Two Pointers O(n^2); O(1)
     * worst case: {1, 3, 5, 7}, 1
     */
    public int numOfSubset(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n; i++) { //必须用for循环枚举最小值
            int left = i, right = n - 1;
            while (left < right) {
                if (nums[left] + nums[right] < target) {
                    count += calculate(left, right);
//                    System.out.println(left + " " + right);
                    break;
                } else {
                    right--;
                }
            }
        }
        return count;
    }

    //比如{1, 3, 5, 7}，min=0,max=3, the subset's number is 2^3-1
    //calculate the number of subsets except the empty set
    //since the subset size is at least 2 and then empty set is not allowed.
    public int calculate(int min, int max) {//min and max are indices
        int k = max - min;
        return (int) Math.pow(2, k) - 1;
//        int res = 0, exp = 1;
//        for (int i = 0; i < k; i++) {
//            res += exp;
//            exp = exp * 2;
//        }
//        return res;
    }

    public static void main(String[] args) {
        SubsetNum test = new SubsetNum();
        int[] nums = {1, 3, 5, 7};//1,3 1,5 1,7 3,5 1,3,5 1,3,7 1,5,7
        int[] nums1 = {2, 7, 11, 15};
        int[] nums2 = {1, 3, 5, 9, 11, 7, 9, 11, 12, 13};
        System.out.println(test.numOfSubset(nums, 9));
    }