491. Increasing Subsequences

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * Backtracking (Recursion). Very similar to Subsets II
 *
 * T(n) = 0 × (n C 0) + 1 × (n C 1) + 2 × (n C 2) + … + n × (n C n)
 *
 * Note that (n C k) = (n C n-k). Therefore:
 *
 * T(n) = 0 × (n C n) + 1 × (n C n-1) + 2 × (n C n-2) + … + n × (n C 0)
 *
 * If we add these two together, we get
 *
 * 2T(n) = n × (n C 0) + n × (n C 1) + … + n × (n C n)
 *
 * = n × (n C 0 + n C 1 + … + n C n)
 *
 * As per binomial theorem, (n C 0 + n C 1 + … + n C n) = 2^n, so
 *
 * 2*T(n) = n * 2^n => T(n) = n * 2^(n-1) = O(n * 2^n)
 *
 * Time Complexity: O(N * 2 ^ N) Refer https://stackoverflow.com/a/20711498
 *
 * Space Complexity: O(N) (Excluding the result space)
 *
 * N = Length of input nums array
 */
class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length < 2) {
            return result;
        }

        backtrack(result, new LinkedList<Integer>(), nums, 0);

        return result;
    }

    private void backtrack(List<List<Integer>> result, LinkedList<Integer> tempList, int[] nums, int start) {
        if (tempList.size() > 1) {
            result.add(new ArrayList<Integer>(tempList));
        }
        HashSet<Integer> numsUsed = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (numsUsed.contains(nums[i])) {
                continue;
            }
            numsUsed.add(nums[i]);
            if (tempList.size() > 0 && tempList.getLast() > nums[i]) {
                continue;
            }
            tempList.add(nums[i]);
            backtrack(result, tempList, nums, i + 1);
            tempList.removeLast();
        }
    }
}