Think about this test case


  • 0
    E

    As far as I know, the simple DP or recursion solution can not solve this test case.

    [1,1073741813]
    1073741823
    Result: 12
    

    Basically, when I saw this problem, I can't assume that the target is small enough to use DP.
    It is quite normal if there is a test case like this:

    [1]
    1073741823
    Result: 1
    

    Simple recursion can't solve this test case too.
    Fortunately, I noticed the return value of method is 'int', so I can assume that the test case like this will not happen:

    [1,2]
    1073741823
    Result: int: out of range
    

    Then the idea comes out. Basically this is the permutation problem, code need to count all the possible result and get the answer. But if the code can find all the combinations, the answer still can be calculated.

    Here is code, I did some optimizations but it is far from perfect:

    public class Solution {
        
        int[] nums;
        HashMap<ArrayList<Integer>, Integer> st;
        
        public int combinationSum4(int[] ns, int target) {
            if (ns == null || ns.length == 0) return 0;
            
            Arrays.sort(ns);
            nums = ns;
            st = new HashMap<>();
            return subSums(ns.length, target, 0);
        }
        
        protected int comb(int a, int b) {
            int N = a + b;
            int K = a > b ? b : a;
            int r = 1;
            for (int i = 1 ; i <= K ; i++) {
                r *= N - i + 1;
                r /= i;
            }
            // System.out.println("C(" + K + "," + N + ")=" + r);
            return r;
        }
        
        protected int subSums(int arraySize, int target, int lineSize) {
            if (target == 0) return 1;
            if (arraySize == 1) {
                if (target % nums[0] == 0) return comb(lineSize, target / nums[0]);
                return 0;
            }
    
            ArrayList<Integer> key = new ArrayList<>();
            key.add(arraySize);
            key.add(target);
            key.add(lineSize);
    
            if (st.containsKey(key)) {
                return st.get(key);
            }
            
            int tot = 0, newItem = 0, factor = 1;
            while (target >= 0) {
                int now = subSums(arraySize - 1, target, lineSize + newItem);
                tot += factor * now;
                target -= nums[arraySize - 1];
                newItem++;
                factor *= lineSize + newItem;
                factor /= newItem;
            }
    
            st.put(key, tot);
            return tot;
        }
    }
    

    Any advices are welcome.


Log in to reply
 

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