LeetCode(79) -- 39, 40, 43

P39. Combination Sum (Medium)

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

The Best Solution

public class P39_CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        combinationSum(ans, new ArrayList<>(), candidates, target, 0);
        return ans;
    }

    private void combinationSum(List<List<Integer>> ans, List<Integer> tempList, int[] candidates, int target, int start) {
        if (target == 0) {
            ans.add(new ArrayList<>(tempList));
            return;
        }
        if (target < 0 || start == candidates.length) {
            return;
        }
        if (candidates[start] <= target) {
            tempList.add(candidates[start]);
            combinationSum(ans, tempList, candidates, target - candidates[start], start);
            tempList.remove(tempList.size() - 1);
        }
        combinationSum(ans, tempList, candidates, target, start + 1);
    }
}

P40. Combination Sum II (Medium)

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

Discuss

public class P40_CombinationSumII {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(ans, new ArrayList<>(), candidates, target, 0);
        return ans;
    }

    private void backtrack(List<List<Integer>> ans, List<Integer> tempList, int[] candidates, int target,  int index) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<>(tempList));
            return;
        }
        for (int i = index; i < candidates.length; i++) {
            if (i > index && candidates[i] == candidates[i - 1]) {
                continue;
            }
            tempList.add(candidates[i]);
            backtrack(ans, tempList, candidates, target - candidates[i], i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = new P40_CombinationSumII().combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5}, 8);
        System.out.println("lists = " + lists);
    }
}

59%

P43. Multiply Strings (Medium)

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Discuss

public class P43_MultiplyStrings {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] pos = new int[m + n];

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + pos[p2];

                pos[p1] += sum / 10;
                pos[p2] = sum % 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int p : pos) {
            if (!(sb.length() == 0 && p == 0)) {
                sb.append(p);
            }
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

85%