Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

**Note:** A leaf is a node with no children.

**Example:**

Given the below binary tree and `sum = 22`

,

5/ \4 8//\11134/\/\ 7251

Return:

[ [5,4,11,2], [5,8,4,5] ]

## Solution

### DFS Approach with Backtracking

/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int x) { val = x; } * } */ public class Solution { public IList<IList<int>> PathSum(TreeNode root, int sum) { var result = new List<IList<int>>(); PathSumHelper(root,result,new List<int>(),sum); return result; } public void PathSumHelper(TreeNode root, IList<IList<int>> result, List<int> list, int sum) { if(root == null) return; list.Add(root.val); if(root.left == null && root.right == null && sum == root.val) { result.Add(new List<int>(list)); } else { PathSumHelper(root.left,result,list,sum-root.val); PathSumHelper(root.right,result,list,sum-root.val); } list.RemoveAt(list.Count-1); } }