排列组合题目，注意递归函数中都有一个base case和一个loop递归的一般情况，和二叉树的题目path sum有点像。

难度: permutations < subsets < combinations < combination sum

subsets和combination sum都有一个指针控制当前数字的位置

• matrix中的path sum，从左上角到右下角dfs:

public static List<List<Integer>> findPath(int[][] grid) {
    // boundary check
    if (grid == null || grid.length == 0 || grid[0].length == 0) return null;

    int m = grid.length;
    int n = grid[0].length;
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(m - 1, n - 1, grid, path, res);
    return res;
}

public static void dfs(int m, int n, int[][] grid, List<Integer> path, List<List<Integer>> res) {
    if (m < 0 || n < 0) return;
    path.add(grid[m][n]);
    if (m == 0 && n == 0)
        res.add(new ArrayList<>(path));
    dfs(m - 1, n, grid, path, res);
    dfs(m, n - 1, grid, path, res);
    path.remove(path.size() - 1);
}

public static void main(String[] args) {
    int[][] grid = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    System.out.println(findPath(grid));
    // [[9, 6, 3, 2, 1], [9, 6, 5, 2, 1], [9, 6, 5, 4, 1], [9, 8, 5, 2, 1], [9, 8, 5, 4, 1], [9, 8, 7, 4, 1]]
}