Path Sum II — DFS Backtracking All Paths

# Python
def pathSum(root, targetSum):
    res = []
    def dfs(node, remaining, path):
        if not node: return
        path.append(node.val)
        if not node.left and not node.right and remaining == node.val:
            res.append(path[:])
        else:
            dfs(node.left, remaining-node.val, path)
            dfs(node.right, remaining-node.val, path)
        path.pop()
    dfs(root, targetSum, [])
    return res

// Java
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
    dfs(root, target, new ArrayList<>());
    return res;
}
void dfs(TreeNode node, int rem, List<Integer> path) {
    if (node==null) return;
    path.add(node.val);
    if (node.left==null&&node.right==null&&rem==node.val) res.add(new ArrayList<>(path));
    else { dfs(node.left,rem-node.val,path); dfs(node.right,rem-node.val,path); }
    path.remove(path.size()-1);
}