Questions tagged [backtracking]
The backtracking tag has no summary.
93 questions
3
votes
2
answers
127
views
Time complexity of a backtracking algorithm
I just solved the following Leetcode problem: All Paths From Source to Target
Here is my solution:
...
- 301
1
vote
1
answer
330
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 ...
CommunityBot
- 1
-2
votes
1
answer
71
views
Can't understand why my algorithm is not correct [DFS AND BACKTRACKING]
I'm trying to solve the following Leetcode problem: https://leetcode.com/problems/path-sum-ii/description/
This solution I came up with is working: https://pastebin.com/ma3DtU5b
However, I was not ...
- 796
1
vote
1
answer
154
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":
...
CommunityBot
- 1
0
votes
1
answer
96
views
Time Complexity of Backtracking solution to Leetcode 473. Matchsticks to Square
The following is a Leetcode problem: 473. Matchsticks to Square (https://leetcode.com/problems/matchsticks-to-square/description/)
Problem Statement
You have an array, matchsticks, of size n, with ...
CommunityBot
- 1
1
vote
1
answer
305
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 ...
D.W.♦
- 169k
2
votes
2
answers
1k
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 ...
8
votes
1
answer
337
views
Branch and bound for minimum linear arrangement
I am trying to solve this branch and bound problem but I could not come up with any approximate cost function which is better than the cost.
Let's say $G$ is a graph of $n$ nodes $\{1, 2, 3, \ldots , ...
0
votes
1
answer
304
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 ...
CommunityBot
- 1
4
votes
0
answers
57
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, ...
- 2,962
1
vote
1
answer
353
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 ...
CommunityBot
- 1
0
votes
0
answers
99
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 ...
3
votes
1
answer
83
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 ...
D.W.♦
- 169k
0
votes
1
answer
98
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.
...
- 717
1
vote
0
answers
53
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 ...
- 111