All Questions
Tagged with combinatorics complexity
13 questions
1
vote
1
answer
381
views
Printing subarrays ⚡
I was trying to to print all subarrays of an array in quadratic time. Here is my code:
...
7
votes
2
answers
812
views
Best Algorithm for solving USACO: Photoshoot - Python
I was trying to solve this problem with Python 3.8. I couldn't find a way other than to brute-force calculate all the possible permutations then check which permutation was valid. The program works ...
- 311
2
votes
1
answer
256
views
Time and Space Complexity of Leetcode Problem #31. Next Permutation
The question is as follows: Given a collection of distinct integers, return all possible permutations. Example:
...
1
vote
1
answer
99
views
Algorithmic complexity of this algorithm to find all ordered permutations of length X
I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars.
For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['...
user168305
3
votes
1
answer
806
views
"Tara's Beautiful Permutations" challenge
I'm practising my coding skills using Python to answer medium to difficult problems on sites like HackerRank.
Here is the challenge. Given an array of integers, where each number can appear at most ...
- 203
3
votes
3
answers
320
views
Finding the number of ways to partition {1,2, ..., N} into p1 and p2 such that sum(p1) == sum(p2)
I am trying to write a space and time efficient algorithm to calculate the number of ways to partition a set of integers {1, 2, ..., N} into two partitions such that the sums of integers in the two ...
- 133
-2
votes
1
answer
3k
views
Counting the number of ways to break an amount into coins
I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations:
quarter: 25 cents
dime: 10 cents
nickel: 5 cents
pennies: 1 cent
There are an ...
- 481
7
votes
3
answers
2k
views
Find the total number of ways W, in which a sum S can be reached in N throws of a dice
I was solving this question:
Given there is a 6 sided dice. Find the total number of ways W, in which a sum S can be reached in N throws.
Example:
S = 1, N = 6 => W = 0
S = 6, N = 6 => W =...
- 1,311
1
vote
2
answers
2k
views
Subset sum simple iterative implementation
Here is the simplest iterative implementation of Subset sum problem that I could come up with1, as a follow up to this recursive implementation of the same problem:
...
- 1,194
2
votes
1
answer
2k
views
Iterative solution for generating all permutations of a string
I know the runtime for generating all permutations is supposed to be \$O(n!)\$. I'm not sure if the code I wrote for it runs in \$O(n!)\$ though. I'm having trouble analyzing its runtime.
The ...
- 331
4
votes
1
answer
13k
views
Permutations of any given numbers
I have solved one programming problem where we have to find all the permutations of given numbers.
For example, \$[1,2,3]\$ have the following permutations:
$$[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,...
- 131
14
votes
1
answer
3k
views
Nonogram puzzle solution space
I've written some code to brute-force enumerate the solution space of nonogram puzzles up to a certain size. It does a good job up to the first ~4 billion puzzles, but I run out of disk space to store ...
user38335
6
votes
2
answers
4k
views
Permutation of given string
I am reading a book on DSA, and the author explains how to generate the permutation of strings using recursion. I want to know if there are better ways of doing the same, unless this is the best ...
