Grade 11 · 12 algorithmsCitește în română

BacktrackingMetoda backtracking

Every backtracking algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

12algorithms
7chapters
1grade

Backtracking

Metoda backtracking · 12 algorithms

Generating arrangements (k-permutations)Generarea aranjamentelorPrints, in lexicographic order, all arrangements of n elements taken k at a time: sequences of k distinct values from {1, ..., n} where order…O(n)
Map coloringColorarea hărțilorA map has n countries numbered from 1, and m pairs (a, b) say that countries a and b are neighbours. We color every country with one of the colors…Exponential
Generating combinationsGenerarea combinărilorPrints all k-element subsets of the set {1, ..., n} (combinations of n taken k at a time). To avoid getting the same subset several times, the…O(n)
Paths in a mazeDrumuri într-un labirintThe maze is an n × m matrix of 0 (free) and 1 (wall). We start in the top-left corner (1, 1) and want to reach the bottom-right corner (n, m),…Exponential
The n-queens problemProblema celor n dameWe place n queens on an n × n board so that none attacks another (no pair on the same row, column or diagonal). We put one queen on every row, and…Exponential
Generating balanced parenthesesGenerarea parantezărilor corectePrints, in lexicographic order ('(' before ')'), all balanced strings made of n pairs of round brackets. We keep the number of brackets opened and…O(n)
Partitions of a natural numberPartițiile unui număr naturalPrints all ways of writing n as a sum of non-zero natural numbers, where the order of the terms does not matter. To avoid repeating the same…Exponential
Permutations with neighbours of alternating parityPermutări cu vecini de parități diferitePrints the permutations of the set {1, ..., n} in which any two neighbouring elements have different parities (one even, the other odd). Compared…Exponential
Generating permutationsGenerarea permutărilorPrints, in lexicographic order, all permutations of the set {1, 2, ..., n}. The solution is built in the array x, position by position. At position…Exponential
Paying a sum with given coinsPlata unei sume cu monede dateThere are n coin types with values v[1..n], as many of each as we want. We print all ways of paying exactly the sum S. x[k] is the number of coins…Exponential
Cartesian productProdusul carteziann sets are given; set i is {1, 2, ..., a[i]}. All elements of the Cartesian product are printed, i.e. all sequences (x1, ..., xn) with 1 ≤ xi ≤…O(n)
Generating subsetsGenerarea submulțimilorPrints all non-empty subsets of the set {1, ..., n}, in lexicographic order. The elements of a subset are placed in strictly increasing order (as…Exponential