Skip to main content

Questions tagged [backtracking]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer
189 views

How to solve a system of XOR equations in a cyclic graph?

I am working on a problem where I need to find values for nodes in a graph of k-nodes. Here an example: The properties are: Each big node (A..H) is connected to at least one blue node Each blue node ...
nowox's user avatar
  • 245
1 vote
0 answers
39 views

Subset sum backtracking algorithm correctness proof

I'm trying to prove that the algorithm for subset sum, that is the algorithm that given a set of numbers $\\{x_1, \dots, x_n\\}$ and a number $K$ find if there is a subset $\\{x_{1_k}, \dots, x_{n_k}\\...
aram's user avatar
  • 111
1 vote
1 answer
54 views

Knapsack Problem: Find Top-K Lower Profit Solutions

In the classic 0-1 knapsack problem, I am using the following (dynamic programming) algorithm to construct a "dp table": ...
slaw's user avatar
  • 111
4 votes
0 answers
37 views

Cardinalities in set coverings

Let $I$ be a set of items; $C \subseteq \mathcal{P}(I)$ be a set of subsets of $I$, where $\mathcal{P}(I)$ stands for the power set of $I$; And $C(i) = \{ c \in C \mid i \in c \}$ be the set of sets, ...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
56 views

Similar problem to Knight's tour

You have board size and one Knight but what is different is that when you move it you have to duplicate the knight and the 2 duplicates have to be in valid position from the knight This gets repeated ...
KnightsProblem's user avatar
3 votes
1 answer
38 views

Trajectories with collisions

Say that I have a plasma gun: It's easy to compute the trajectory of the plasma ray starting from the gun. However, another ray may come from afar: As everybody knows, plasma rays are deviated when ...
cdupont's user avatar
  • 131
0 votes
1 answer
61 views

Doubts in backtracking function animation, for call sequence flow

In the slides' based animation given for backtracking, here (with code here, in the web-page ); have few doubts, in the code restated below, and the execution as shown in the call #5. ...
jiten's user avatar
  • 187
2 votes
2 answers
454 views

Ways to speed up a Recursive Backtracking Algorithm

When dealing with a Recursive Backtracking Algorithm what are the ways to speed it up and what computational hardware is involved? I'm assuming from ignorance that everything is done by the CPU so the ...
Daviid's user avatar
  • 123
1 vote
0 answers
30 views

generating solvable puzzles for a Double-Choco puzzle game. efficient data structure and algorithm to be used in? [closed]

I'm working on implementing a puzzle board game called Double-Choco published by Nikoli magazine Where the board is a 2-dimensional matrix with cells that are either white or gray. The goal is to ...
Muhammad Z's user avatar
1 vote
1 answer
131 views

fastest algorithm to count leaf nodes (i.e. terminal nodes)

With the following recursive code to count leaf nodes of a binary tree, is there any way to make it faster or parallel-computing optimized in time? Python code - (mag(P) = number of leaf nodes of tree ...
Ten's user avatar
  • 119
0 votes
2 answers
50 views

How do I keep track of different ways I can structure a 2D array

As of recently I've been trying to get better at algorithms and I've stumbled onto one that I can't seem to solve. The idea behind the algorithm is to try to find as many different ways as possible to ...
JohnA's user avatar
  • 101
0 votes
1 answer
153 views

Suggest good books for Advanced Data Structure and Algorithms

I don't really need hands on coding help, I need to clear my concepts of some of the more complex topics of DS and Algo like NP-Completeness, Computational Geometry, String Matching, Multithreaded ...
azwadkm22's user avatar
0 votes
1 answer
246 views

How to find average time complexity of backtracking algorithm?

Problem is to decide if it is possible to partition a given array nums into k partitions. I've written a brute force backtracking algorithm. How do we analyse this algorithm to calculate average ...
Ajax's user avatar
  • 163
2 votes
1 answer
188 views

Runtime complexity of permutation function

I am trying to find the asymptotic run time complexity of the following function which will return a list of all permutations of nums. ...
user1234's user avatar
1 vote
1 answer
232 views

Given a sequence of strings how can you find the maximum number of strings so that if you concatenate them you have a dominant letter?

The naive approach, which is the first thing that came to my mind, is to use some sort of backtracking to generate all subsets of the given set of strings and then to find the subset with the maximum ...
jakeprog123's user avatar
1 vote
1 answer
774 views

Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized

Let's say we have a set of n integers. I'm trying to find a way to partition this set into m subsets (empty subsets are not ...
Fish_n_Chips's user avatar
1 vote
0 answers
19 views

Find optimal starting point of recursive search, with solution known

An Exact Cover problem is commonly denoted as a matrix of 0s and 1s. Columns denote requirements, rows denote possible choices. The problem is solved when a set of rows was found such that, using just ...
mafu's user avatar
  • 339
0 votes
1 answer
151 views

Time Complexity - Palindrome Partition

I am solving an interview practice question: Partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. My solution is as below, and was ...
capybara's user avatar
1 vote
0 answers
1k views

Minimum no of swaps to be done in an array such that, no two adjacent elements are same

Given an array of size n, find minimum number of swaps required, so that no two adjacent elements are equal. For ex- n = 6, a[] = {1, 1, 5, 2, 5, 5}, answer = 1, ( swap a[0] with a[4] or a[5] ) n = 8,...
code_it's user avatar
  • 31
0 votes
0 answers
21 views

How do I group elements of a list into windows of predefined sizes with minimum cost given longer windows are cost efficient?

You are given a list of days numbered 0 to 365 in the calendar year where you need to be in a hotel. You need to book in advance for the year and need not necessarily be there when you have a booking. ...
Mihir's user avatar
  • 1
0 votes
0 answers
96 views

Complexity of backtracking to find power set given random array of numbers

Given an array of elements which can contain duplicates, this is an algorithm that solves the problem. ...
OnePiece's user avatar
  • 123
2 votes
2 answers
850 views

Longest sequence of dominoes

Given $k$, a $k$-domino is a non-ordered pair of integer values of $[\![0, k-1]\!]$, for example $\langle 0, 3\rangle$ or $\langle 1, 1\rangle$ are dominoes, the domino $\langle 3, 0\rangle$ being the ...
Nathaniel's user avatar
  • 15.8k
-2 votes
1 answer
308 views

recurrence relation for this n queen problem algorithm . and the time complexity

I am not able to understand how to write a recurrence relation for this n queen problem algorithm down below. Recurrence relation is for n*n board and the time complexity ...
Zero One's user avatar
0 votes
0 answers
131 views

How to solve this combinatoric problem without bruteforce

I'm trying to solve the following problem : A tile results of a number and a color. a tile can be black, red, orange or blue. a tile number is >= 1 and <= 15. Given a random set a tiles (a ...
poivron64's user avatar
0 votes
0 answers
29 views

I need good book about algorithms, which explains recursion, backtracking and depth first recursion for beginners [duplicate]

I'm learning programming, Python 3 in particular, and I have a good book "Beginning Python - From Novice to Professional" by Magnus Lie Hetland, but the book doesn't explain algorithms at ...
Fandi Bataineh's user avatar
1 vote
2 answers
683 views

Best approach to resource allocation problem

Problem The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city ...
user2891462's user avatar
1 vote
1 answer
361 views

Why is backtracking a necessary step in the Maze problem?

The problem I am working on is specifically this: A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower ...
a_sid's user avatar
  • 113
0 votes
0 answers
40 views

Maximize Possible Subset Sums of A Multiset

The following problem is a problem I faced in one of my coding competitions. Given two positive integers $N$, $M$. You can have $M$ distinct types of stones, for which different types of stones must ...
user9989615's user avatar
0 votes
0 answers
80 views

Number of Hamilton paths in graphs

I am trying to find a fast algorithm that can compute the number of hamiltonian paths in an undirected graph. I saw this on the web, but it sounds like this finds all hamiltonian paths starting from ...
K.N's user avatar
  • 101
1 vote
1 answer
60 views

Does this LCS algo generate all the CS or only all the LCSs?

The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-...
oldsailorpopoye's user avatar
0 votes
0 answers
38 views

Problem with the algorithm

I am trying to execute the following algorithm shown in the image from my course slide. I am trying to get the table shown in the image: 1st Iteration L2: 1:CS=A, SL = A, NSL = A L3: while NSL!=[]: ...
user2994783's user avatar
2 votes
0 answers
43 views

Choosing a method for algorithmic problems - is it an art or science?

I've been doing lot of programming challenges lately (such as on leetcode.com) and often find myself in a situation when I cannot pick a method for solving a problem. I stuck with questions like - ...
averbin's user avatar
  • 121
0 votes
0 answers
102 views

Extending a solution in backtracking

Steven Skiena's "Algorithm Design Manual" has the following code for the backtracking algorithm: ...
ved's user avatar
  • 101
1 vote
2 answers
1k views

Does DFS have better constants/complexity than Backtracking on a Graph?

I came to know through some examples that DFS and Backtracking aren't exactly the same ( A misconception I had since a long time). So now my question is, since Backtracking visits nodes backwards step ...
Hrishikesh Athalye's user avatar
0 votes
0 answers
80 views

The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
user35443's user avatar
  • 213
1 vote
1 answer
122 views

Can the algorithm be optimized?

I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach ...
Spindoctor's user avatar
3 votes
0 answers
1k views

Backtracking vs Branch-and-Bound

I'm getting a bit confused about the three terms and their differences: Depth-First-Search (DFS), Backtracking, and Branch-and-Bound. What confuses me: Stack Overflow: Difference between '...
Martin Thoma's user avatar
  • 2,360
0 votes
1 answer
55 views

Why N-Queens Problem is not used as experiment in CSP thesis?

I am studying CSP for my master thesis. I found that many thesis based on CSP described N-Queens as an introductory and they actually do experiment on random CSP problems. If so,when I do master ...
Cecelia's user avatar
  • 53
2 votes
2 answers
236 views

Need recursive version of Conflict based backjumping

I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach? In AIMA they give the recursive ...
Cecelia's user avatar
  • 53
0 votes
1 answer
831 views

Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour

I have implemented the basic algorithm. easily available but I am not getting the complete tour. The visited square never equals N * N;
agamjain14's user avatar
1 vote
2 answers
1k views

Line-search does not guarantee convergence so how to use it?

Line-search/backtracking in gradient descent methods essentially boils down to picking the current estimate $\theta_n$ (which depends on the stepsize $\gamma$ and the prior estimate $\theta_{n-1}$) by ...
FiexPriceo's user avatar
0 votes
2 answers
2k views

How to generate all combinations given an array of elements using backtracking?

Given an array, generate all combinations For example: Input: {1,2,3} Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} I am ...
Instinct's user avatar
  • 101
1 vote
0 answers
353 views

How to approach backtracking when using immutable types (Python)? [closed]

In Python when we are building a recursive algorithm that uses backtracking a mutable type such as a list is great to use. It can be modified at each call in our recursion tree, then returned back to ...
Daniel's user avatar
  • 11
1 vote
0 answers
42 views

How to rule bactrack research on alphametric puzzles?

I have a funny aphametic problem: I A + I A ----- P B I have to find which are the values of the letters. I know I can try backtrack with forward research, MRV ...
Revolucion for Monica's user avatar
1 vote
1 answer
41 views

Cracking code with clues

I am trying to solve this code cracking problem. The solution is either the code or all possible solutions if you can't narrow the possibilities. We have a 5 character code that is consisting of ...
james F.'s user avatar
  • 111
3 votes
2 answers
104 views

Maximize number of museums visited in a day

Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day. Suppose that no time is needed in ...
Stefan Borović's user avatar
0 votes
2 answers
757 views

Why run -time of N-Queens using backtracking algorithm fluctuates?

I have tested and measured the running time of a backtracking algorithm for solving the $N$-Queens problem. When $N=7$, the run time is $0.773$, but for $N=8$, the run time is $0.492$. I think the ...
Cecelia's user avatar
  • 53
0 votes
1 answer
228 views

Help with graph search problem

For the next problem I can not think of how to find a solution with graph searches (I thought it was backtracking but my college professor told me that I should use graph searches, which I do not know ...
FredieF's user avatar
  • 31
1 vote
1 answer
162 views

Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?

Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem? I saw this Gurobi post that uses Integer Linear Programming to solve the traveling ...
Andrea Nardi's user avatar
1 vote
1 answer
344 views

How to count the combinations not greater than a given volume in a knapsack problem?

You are given a certain set of items with weight wi and the volume of the bag. Case: ...
Hearen's user avatar
  • 113