Long Luo's Life Notes

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> ans = new ArrayList<>();

    // corner cases
    if (k <= 0 || n <= 0 || k > n) {
        return ans;
    }

    // The upper bound of n: [9, 8, ... , (9 - k + 1)], sum is (19 - k) * k / 2
    if (n > (19 - k) * k / 2) {
        return ans;
    }

    backtrack(ans, new ArrayList<>(), 1, k, n);
    return ans;
}

public void backtrack(List<List<Integer>> res, List<Integer> path, int start, int k, int target) {
    if (k < 0 || target < 0) {
        return;
    }

    if (k == 0 && target == 0) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i <= 9; i++) {
        // trim 
        if (i > target) {
            break;
        }
			
        // trim
        if (target - i == 0 && k > 1) {
            break;
        }

        path.add(i);
        backtrack(res, path, i + 1, k - 1, target - i);
        path.remove(path.size() - 1);
    }
}

public static List<String> letterCombinations_4Loops(String digits) {
    List<String> ans = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return ans;
    }

    String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int len = digits.length();
    int[] digitsArr = new int[len];
    for (int i = 0; i < len; i++) {
        digitsArr[i] = digits.charAt(i) - '0';
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < len; i++) {
        sb.append("a");
    }

    for (int i = 0; i < letters[digitsArr[0] - 2].length(); i++) {
        sb.replace(0, 1, letters[digitsArr[0] - 2].charAt(i) + "");
        if (len == 1) {
            ans.add(sb.substring(0, 1));
        }

        for (int j = 0; len >= 2 && j < letters[digitsArr[1] - 2].length(); j++) {
            sb.replace(1, 2, letters[digitsArr[1] - 2].charAt(j) + "");
            if (len == 2) {
                ans.add(sb.toString());
            }

            for (int k = 0; len >= 3 && k < letters[digitsArr[2] - 2].length(); k++) {
                sb.replace(2, 3, letters[digitsArr[2] - 2].charAt(k) + "");
                if (len == 3) {
                    ans.add(sb.toString());
                }

                for (int l = 0; len >= 4 && l < letters[digitsArr[3] - 2].length(); l++) {
                    sb.replace(3, 4, letters[digitsArr[3] - 2].charAt(l) + "");
                    ans.add(sb.toString());
                }
            }
        }
    }

    return ans;
}

public class NestedIterator implements Iterator<Integer> {
    List<Integer> numList;
    int idx;

    public NestedIterator(List<NestedInteger> nestedList) {
        numList = new ArrayList<>();
        idx = 0;
        dfs(nestedList);
    }

    private void dfs(List<NestedInteger> nestedList) {
        if (nestedList == null) {
            return;
        }

        for (int i = idx; i < nestedList.size(); i++) {
            NestedInteger nested = nestedList.get(i);
            if (nested.isInteger()) {
                numList.add(nested.getInteger());
            } else {
                dfs(nested.getList());
            }
        }
    }

    @Override
    public Integer next() {
        return numList.get(idx++);
    }

    @Override
    public boolean hasNext() {
        if (idx < numList.size()) {
            return true;
        }

        return false;
    }
}

public boolean find132pattern_bf(int[] nums) {
    int len = nums.length;
    if (len < 3) {
        return false;
    }

    for (int i = 0; i < len - 2; i++) {
        for (int j = i + 1; j < len - 1; j++) {
            for (int k = j + 1; k < len; k++) {
                if (nums[i] < nums[k] && nums[k] < nums[j]) {
                    return true;
                }
            }
        }
    }

    return false;
}