Java DFS and HashMap


  • 0
    V

    Can use an array instead, for a faster time.

    public class Solution 
    {
        HashMap<Integer, Integer> hm;
        public int combinationSum4(int[] nums, int target) 
        {
            if(nums == null || nums.length == 0)
                return 0;
            Arrays.sort(nums);
            hm = new HashMap<Integer, Integer>();
            int cnt = 0;
            for(int i = 0; i < nums.length; i++)
                cnt += dfs(nums, i, nums[i], target);
            return cnt;
        }
        int dfs(int[] nums, int ind, int currSum, int target)
        {
            if(hm.containsKey(currSum))
                return hm.get(currSum);
            if(currSum == target)
            {
                hm.put(currSum, 1);
                return 1;
            }
            int cnt = 0;
            for(int i = 0; i < nums.length; i++)
            {
                if(currSum + nums[i] > target)
                    break;
                cnt +=dfs(nums, i, currSum + nums[i], target);
            }
            hm.put(currSum, cnt);
            return cnt;
        }
    }

Log in to reply
 

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