1144. Number of Paths with Sum K in Grid

Given a grid of non-negative integers and a target k, count the paths from the top-left to the bottom-right (moving only right or down) whose collected sum equals exactly k. The input is JSON {grid, k}.

Input: JSON {grid, k}.

Output: Integer — the number of paths summing to k.

Examples

Input: {"grid":[[1,2,3],[4,5,6]],"k":12}
Output: 1
Explanation: Only 1->2->3->6 sums to 12.

Input: {"grid":[[1,1],[1,1]],"k":3}
Output: 2
Explanation: Both paths sum to 3.

Input: {"grid":[[5]],"k":5}
Output: 1
Explanation: Single cell matches.

Constraints

• 1<=rows,cols<=20
• 0<=k<=10^4

Asked by