ब्याकट्र्याकिङ आंशिक समाधानहरूलाई क्रमशः निर्माण गर्दछ र त्यागदछ (यदि यो वैध समाधान तिर अग्रसर हुन सक्दैन भने त्यहाँबाट फर्किन्छ)। यसले DFS मार्फत समाधान स्पेसको क्रमबद्ध अन्वेषण गर्दछ, मृत अन्तहरूलाई काटदै।
विचार
छनौट गर्नुहोस् -> अन्वेषण गर्नुहोस् -> छनौट हटाउनुहोस्। एक विकल्प प्रयास गर्नुहोस्, पुनरावृत्ति गर्नुहोस्; यदि यो असफल हुन्छ, यसलाई पूर्ववत गर्नुहोस् र अर्को प्रयास गर्नुहोस्।
उदाहरण: सबै क्रमपरिवर्तन
python
():
result = []
():
remaining:
result.append(path[:])
i ((remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+:])
path.pop()
backtrack([], nums)
result
permutations([, , ])