Add Operators

http://www.lintcode.com/en/problem/add-operators/

public class Solution {
    /*
     * @param num: a string contains only digits 0-9
     * @param target: An integer
     * @return: return all possibilities
     */
    List<String> res; 
    String num;
    int target;

    public List<String> addOperators(String num, int target) {
        // write your code here
        res = new ArrayList<>();
        this.num = num;
        this.target = target;

        dfs(0, "", 0, 0);

        return res;
    }

    private void dfs(int start, String str, long sum, long last){
        if(start == num.length()){
            if(sum == target){
                res.add(new String(str));    
            }
            return;
        }

        for(int i = start; i < num.length(); i++){
            long val = Long.parseLong(num.substring(start, i + 1));

            if(start == 0){
                dfs(i + 1, str + val, val, val);
            }else{
                dfs(i + 1, str + "+" + val, sum + val, val);
                dfs(i + 1, str + "-" + val, sum - val, -val);
                dfs(i + 1, str + "*" + val, sum - last + last * val, last * val);
            }

            if(num.charAt(start) == '0'){
                break;
            }
        }
    }
}

Factorization

http://www.lintcode.com/zh-cn/problem/factorization/

public class Solution {
    /**
     * @param n an integer
     * @return a list of combination
     */

    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    void dfs(int start, int remain) {
        if (remain == 1) {
            if (path.size() != 1) {
                ans.add(new ArrayList<>(path)); //deep copy
            }
            return;
        }

        for (int i = start; i <= remain; i++) {
            if (i > remain / i) {
                break;
            }
            if (remain % i == 0) {
                path.add(i);                  //进栈
                dfs(i, remain / i);
                path.remove(path.size() - 1); //出栈
            }
        }

        path.add(remain);
        dfs(remain, 1);
        path.remove(path.size() - 1);
    }

    public List<List<Integer>> getFactors(int n) {
        // write your code here
        dfs(2, n);
        return ans;
    }
}