The power of optimization in backtracking


  • 0
    J

    Witness the importance of optimization in backtracking

    public class Solution {
        void dfs(int level, int k, int n, List<Integer> ans, List<List<Integer>> res) {
            if (level==k) {
                res.add(new ArrayList(ans));
                return;
            }
            int ansSize = ans.size();
            int lastDigit = ans.isEmpty()?0:ans.get(ansSize-1);
            if (ansSize+(n-lastDigit)<k) {  //This line is a game changer, the beat time increases from 2% to 90%.
                return;
            } else {
                for (int i=lastDigit+1; i<n+1; i++) {
                    ans.add(i);
                    dfs(level+1, k, n, ans, res);
                    ans.remove(ans.size()-1);
                }
            }
            return;
        }
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> res = new ArrayList<>();
            dfs(0, k, n, new ArrayList<>(), res);
            return res;
        }
    }
    

Log in to reply
 

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