54cd011e.8c37cceb.js

(window.webpackJsonp=window.webpackJsonp||[]).push([[28],{102:function(e,n,t){"use strict";t.r(n),t.d(n,"frontMatter",(function(){return s})),t.d(n,"metadata",(function(){return u})),t.d(n,"toc",(function(){return m})),t.d(n,"Backtracking",(function(){return d})),t.d(n,"default",(function(){return p}));var a=t(147),i=t(149),r=t(0),o=t.n(r),c=t(148),l=t(200),s={id:"Introduction",title:"Introduction to Backtracking",sidebar_label:"Introduction to Backtracking"},u={unversionedId:"Patterns/Backtracking/Introduction",id:"Patterns/Backtracking/Introduction",isDocsHomePage:!1,title:"Introduction to Backtracking",description:"Have you ever run into these problems in your daily life?",source:"@site/docs/Patterns/Backtracking/Introduction.md",slug:"/Patterns/Backtracking/Introduction",permalink:"/docs/Patterns/Backtracking/Introduction",version:"current",sidebar_label:"Introduction to Backtracking",sidebar:"Patterns",next:{title:"Permutation of Elements",permalink:"/docs/Patterns/Backtracking/Permutation/Permutation"}},m=[{value:"Backtracking",id:"backtracking",children:[]},{value:"Intuitions of A Backtracking Problem",id:"intuitions-of-a-backtracking-problem",children:[]},{value:"Backtracking Generalized Solution Template",id:"backtracking-generalized-solution-template",children:[]},{value:"References",id:"references",children:[]}],d=function(){return Object(c.b)(o.a.Fragment,null,"undefined"!=typeof window&&Object(c.b)(l.c,{data:{name:"\ud83e\udd43",children:[{name:"Bourbon",children:[{name:"Mint",children:[{name:"Mint Julep"}]},{name:"Vermouth",children:[{name:"Manhattan"}]},{name:"Lime",children:[{name:"Cherry",children:[{name:"Whiskey Sour"}]}]},{name:"Ice Cube",children:[{name:"Orange Peel",children:[{name:"Old Fashioned"}]}]}]},{name:"Vodka",children:[{name:"Tomato",children:[{name:"Bloody Mary"}]},{name:"Kahlua",children:[{name:"Cream",children:[{name:"White Russian"}]}]},{name:"Cranberry",children:[{name:"Grapefruit",children:[{name:"Sea Breeze"},{name:"Lime",children:[{name:"Cosmopolitan"}]}]}]}]},{name:"Rum",children:[{name:"Pineapple",children:[{name:"Coconut",children:[{name:"Pina Colada"}]}]},{name:"Lime",children:[{name:"Mojito"},{name:"Cola",children:[{name:"Cuba Libre"}]}]}]}]},mdxType:"TreeChart"}))},b={toc:m,Backtracking:d};function p(e){var n=e.components,t=Object(i.a)(e,["components"]);return Object(c.b)("wrapper",Object(a.a)({},b,t,{components:n,mdxType:"MDXLayout"}),Object(c.b)("p",null,"Have you ever run into these problems in your daily life?"),Object(c.b)("ul",null,Object(c.b)("li",{parentName:"ul"},"For my luggage lock, what are some of the interesting password combination I can come up with? \ud83d\udd10"),Object(c.b)("li",{parentName:"ul"},"For my living room, how many possible ways I can rearrange my sofa, table, speakers and TV? \ud83d\udcfa"),Object(c.b)("li",{parentName:"ul"},"Or, yes! this is a good one, given a set of liquors and juice, what are possible cocktails I can come up with? \ud83c\udf79")),Object(c.b)(d,{mdxType:"Backtracking"}),Object(c.b)("h2",{id:"backtracking"},"Backtracking"),Object(c.b)("blockquote",null,Object(c.b)("p",{parentName:"blockquote"},'"Backtracking can be defined as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem."')),Object(c.b)("h2",{id:"intuitions-of-a-backtracking-problem"},"Intuitions of A Backtracking Problem"),Object(c.b)("ol",null,Object(c.b)("li",{parentName:"ol"},'The problem is about combinations, combinatorics, and permutation. Usually the problem has multiple possible solutions and it asks you to "list" or "enumerate" all the possible solutions.'),Object(c.b)("li",{parentName:"ol"},"When you try to come up with an combination of both iteration and recursion. For example, you need to have a loop inside of a recursive function, and the loop's range depends on the function parameters:")),Object(c.b)("pre",null,Object(c.b)("code",Object(a.a)({parentName:"pre"},{className:"language-java"}),"void someRecursiveFunction(int x, int y){\n    /* do something... */\n    for(int i = 0; i < y; i++){\n        /* do something in the for loop... */\n        // call someRecursiveFunction with updated parameters\n        someRecursiveFunction(x, y+i);\n    }\n    /* do something else... */\n}\n")),Object(c.b)("ol",{start:3},Object(c.b)("li",{parentName:"ol"},"When you can prove that the solution needs a runtime of ",Object(c.b)("img",{src:"https://render.githubusercontent.com/render/math?math=O(n!)"}))),Object(c.b)("h2",{id:"backtracking-generalized-solution-template"},"Backtracking Generalized Solution Template"),Object(c.b)("pre",null,Object(c.b)("code",Object(a.a)({parentName:"pre"},{className:"language-java"}),"class Solution {\n    /* Declare private data structures: */\n    private ArrayList<Integer> solutions;\n    public List<List<Integer>> permute(int[] nums) {\n        // declare private data structures\n        solutions = new ArrayList<>();\n        // call backtrack\n        backtrack(param1, param2);\n        // return results\n        return this.results;\n    }\n\n    private void backtrack(int param1, int param2){\n        // handle base case!\n        if(BaseCase qualified){\n            // Add current result to the solution collection\n            solutions.add(param2)\n            return;\n        }\n\n        for(int i = 0; i< param1; i++){\n            // 1. Handle edge case\n            if(count[i] == 0) continue;\n            // 2. Prepare a possible solution using some variable\n            result.set(level, nums[i]);\n            // 3. Remove used variable in step 2\n            count[i]--;\n            // 4. Call backtrack recursively\n            backtrack(param1, param2+1);\n            // 5. Add used variable in step 2 and 4 back to the set\n            count[i]++;\n        }\n    }\n}\n")),Object(c.b)("h2",{id:"references"},"References"),Object(c.b)("ul",null,Object(c.b)("li",{parentName:"ul"},Object(c.b)("a",Object(a.a)({parentName:"li"},{href:"https://www.geeksforgeeks.org/backtracking-introduction/"}),"Geeksforgeeks: Intro to Backtracking"))))}p.isMDXComponent=!0}}]);