Easy Java O(1) space DFS Solution


  • 0
    I
    int sum;
    public int pathSum(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        helper(nums, 1, 1, 0, 0);
        return sum;
    }
    
    private void helper(int[] nums, int hundred, int tens, int idx, int s) {
        boolean nonleave = false;
        for (int i = idx; i < nums.length; i++) {
            int h = nums[i] / 100;
            if (h == hundred) {
                int v = (nums[i] / 10) % 10;
                if (v == 2 * tens - 1 || v == 2 * tens) {
                    helper(nums, hundred + 1, v, i + 1, s + nums[i] % 10);
                    nonleave = true;
                }
            } else if (h > hundred){
                break;
            }
        }
        if (!nonleave) {
            sum += s;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.